求构造一组 Hack 数据，指出错误之处最好
本帖最后由 zhangjinxuan 于 2023-7-18 22:06 编辑题目：https://atcoder.jp/contests/abc137/tasks/abc137_e
友好翻译（来源洛谷）：
有一个有向图，点的编号为 1~N，有 M 条边，每条边为 a i →b i ，这条边上有 c i枚硬币。
您从节点1 开始移动，初始硬币为 0，你需要抵达 N，经过每条边耗时 1 分钟，每次经过一条边你都能收获硬币，无论重复多少次。
当您抵达 N 节点时，你可以结束游戏，也可以继续游戏，但是当你结束游戏的时候，你需要支付T×P 枚硬币 （T表示时间），当您的硬币少于这个值时，你需要支付全部的硬币。
你的分数就是在付款后所拥有的硬币数量，如果可以确定能获得一个最大分数，你需要输出可以获得的分数的最大值。
主要思路：
DP，感觉很奇怪。
你先别急，让我先急，首先，因为答案会减去 T * P，也就是说，走一步就会减去 P 的金币，那就把所有边权都减 P。
然后，定义状态 f j,i 表示使用 j 步走到 i 节点的最大收益。
转移就是使用 j - 1 步到达所有可以到达 i 的边 + 这条边权。
特判没有走到的情况。
处理 -1 的情况就是，如果当前走了 n 以上的步仍然在更新 f[] 的值，就说明不存在最大值。
码量不多，下面是我的代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
long long f, ans = -1ll << 60, p, z;
struct Edge {
int to;
long long l;
};
vector<Edge> edges;
int main() {
scanf("%d%d%lld", &n, &m, &p);
while (m--) {
scanf("%d%d%lld", &x, &y, &z);
edges.push_back({x, z - p});
}
memset(f, 128, sizeof(f));
f = 0;
for (int j = 1; j <= n + n; ++j) {
for (int i = 1; i <= n; ++i) {
for (auto k : edges) {
if (f == f) continue;
f = max(f, f + k.l);
}
if (i == n && f > ans) {
if (j >= n) {
puts("-1");
return 0;
}
ans = f;
}
}
}
printf("%lld\n", max(ans, 0ll));
return 0;
}
结果：https://atcoder.jp/contests/abc137/submissions/43729012
After Contest 全 WA，而且通过特殊方法，我发现 After Contest 全是 -1，是 -1 这一块没有处理好吗？ 根据题目描述和代码分析，该问题是一个动态规划（DP）的最优路径问题。代码中使用了二维数组 f 来表示使用 j 步走到 i 节点的最大收益。但在代码中，对 f 数组进行初始化时，使用了 memset(f, 128, sizeof(f))，将 f 数组的值都设置为一个很小的负数。
问题出现在这里，因为后续代码中将 f 的值与其他数相加，并且使用 max 函数进行比较，如果初始值太小，可能会导致最终结果的比较出错。另外，题目中要求输出的是最大分数而非最小收益，所以初始值应设为一个很小的负无穷大。
要解决这个问题，你需要将代码中的初始化部分修改为 memset(f, -1, sizeof(f))，将 f 数组的初始值设为 -1，表示还没有计算。
修改后的代码如下所示：
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
long long f, ans = -1ll << 60, p, z;
struct Edge {
int to;
long long l;
};
vector<Edge> edges;
int main() {
scanf("%d%d%lld", &n, &m, &p);
while (m--) {
scanf("%d%d%lld", &x, &y, &z);
edges.push_back({x, z - p});
}
memset(f, -1, sizeof(f));
f = 0;
for (int j = 1; j <= n + n; ++j) {
for (int i = 1; i <= n; ++i) {
for (auto k : edges) {
if (f == -1)
continue;
f = max(f, f + k.l);
}
if (i == n && f > ans) {
if (j >= n) {
puts("-1");
return 0;
}
ans = f;
}
}
}
printf("%lld\n", max(ans, 0ll));
return 0;
}
通过这样的修改，可以解决初始值设置不当导致的错误。希望这能解决你的问题，如果还有其他疑问，请随时提问。 你的代码有一个小问题，主要在处理存在负环的情况上。由于负环可以无限制地提供硬币，因此在存在负环的情况下，应当输出 -1。
然而，你的代码只在 j（步数）达到或超过节点数（n）时判断是否存在负环，这并不正确。因为这样的话，可能会漏掉一些步数少于 n，但是已经形成了负环的情况。
你的负环判断应该在对每个 j 进行动态规划时都检查。如果在一个状态的硬币数量比前一个状态的硬币数量多，并且该状态所在的步数大于或等于 n，那么就可以判断存在负环。
你可以尝试将你的代码修改如下：
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
long long f, ans = -1ll << 60, p, z;
struct Edge {
int to;
long long l;
};
vector<Edge> edges;
int main() {
scanf("%d%d%lld", &n, &m, &p);
while (m--) {
scanf("%d%d%lld", &x, &y, &z);
edges.push_back({x, z - p});
}
memset(f, 128, sizeof(f));
f = 0;
for (int j = 1; j <= n + n; ++j) {
for (int i = 1; i <= n; ++i) {
for (auto k : edges[ i]) {
if (f == f) continue;
f[ i] = max(f[ i], f + k.l);
}
if (i == n) {
if (j >= n && f[ i] > f[ i]) {
puts("-1");
return 0;
}
ans = max(ans, f[ i]);
}
}
}
printf("%lld\n", max(ans, 0ll));
return 0;
}
这个修正的代码中，每个状态都将被检查是否存在负环，只要在步数 j 大于等于 n 的状态中，如果发现当前步的硬币数量比上一步的硬币数量多，就可以判断存在负环，并输出 -1。如果没有负环，将像原来的代码一样，输出最大的硬币数量。
希望这个答案可以帮助到你，如果你还有其他问题，欢迎继续提问。 isdkz 发表于 2023-7-18 22:06
你的代码有一个小问题，主要在处理存在负环的情况上。由于负环可以无限制地提供硬币，因此在存在负环的情况 ...
很好，After Contest（子任务） 通过，但是 All 子任务 WA 了 14 个测试点。
https://atcoder.jp/contests/abc137/submissions/43729232
我虽然知道你是 ChatGPT，但还是希望能通过你来解决问题。 陶远航 发表于 2023-7-18 22:06
根据题目描述和代码分析，该问题是一个动态规划（DP）的最优路径问题。代码中使用了二维数组 f 来表示使 ...
WA的次数更多了 zhangjinxuan 发表于 2023-7-18 22:10
WA的次数更多了
让我的gpt试一试{:10_256:} zhangjinxuan 发表于 2023-7-18 22:09
很好，After Contest（子任务） 通过，但是 All 子任务 WA 了 14 个测试点。
https://atcoder.jp/cont ...
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
long long f, ans = -1ll << 60, p, z;
struct Edge {
int to;
long long l;
};
vector<Edge> edges;
int main() {
scanf("%d%d%lld", &n, &m, &p);
while (m--) {
scanf("%d%d%lld", &x, &y, &z);
edges.push_back({x, z - p});
}
memset(f, 128, sizeof(f));
f = 0;
for (int j = 1; j <= 2 * n; ++j) {
for (int i = 1; i <= n; ++i) {
for (auto k : edges) {
if (f == f) continue;
f = max(f, f + k.l);
}
if (i == n && f > ans) {
if (j >= 2 * n) {
if (f > f) {
puts("-1");
return 0;
}
}
ans = f;
}
}
}
printf("%lld\n", max(ans, 0ll));
return 0;
}
我的比他强，11个{:10_256:} sfqxx 发表于 2023-7-18 22:17
我的比他强，11个
寄 zhangjinxuan 发表于 2023-7-18 22:18
寄
啥？ isdkz 发表于 2023-7-18 22:06
你的代码有一个小问题，主要在处理存在负环的情况上。由于负环可以无限制地提供硬币，因此在存在负环的情况 ...
GPT的思路是正确的，代码错了{:10_277:} zhangjinxuan 发表于 2023-7-18 22:35
GPT的思路是正确的，代码错了
{:10_266:}
页:
[1]