@[realskc](/user/35672) @[installb](/user/31440)
by ivyjiao @ 2024-02-18 14:52:33
@[ivyjiao](/user/578029) 虽然但是,我按照这个写过了你的数据。。。
```
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 5010,M = 2 * N;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
LL dist[N];
int cnt[N];
bool st[N];
void add (int a,int b,int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
bool spfa () {
memset (dist,-0x3f,sizeof (dist));
dist[1] = 0;
queue <int> q;
for (int i = 1;i <= n;i++) {
q.push (i);
st[i] = true;
}
while (q.size ()) {
int t = q.front ();
q.pop ();
st[t] = false;
for (int i = h[t];~i;i = ne[i]) {
int j = e[i];
if (dist[j] < dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j]++;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.push (j);
st[j] = true;
}
}
}
}
return false;
}
int main () {
memset (h,-1,sizeof (h));
cin >> n >> m;
while (m--) {
int op,a,b;
cin >> op >> a >> b;
if (op == 1) {
int c;
cin >> c;
add (b,a,c);
}
else if (op == 2) {
int c;
cin >> c;
add (a,b,-c);
}
else add (a,b,0),add (b,a,0);
}
if (spfa ()) puts ("No");
else puts ("Yes");
return 0;
}
```
by incra @ 2024-02-18 14:58:38
@[incra](/user/463956) 那我就不知道咋回事了(
by ivyjiao @ 2024-02-18 15:01:47
@[ivyjiao](/user/578029) 而且你 hack 问题不止在加边,还在于没有跑最长路
by incra @ 2024-02-18 15:02:16
而且反着加边跑最短路应该也是可以的。
by incra @ 2024-02-18 15:03:09
你这改完还是错的……OI wiki 代码跑的是最长路,应该是:
```cpp
if (op == 1) {
scanf("%d%d%d", &x, &y, &z);
addedge(x, y, z);
} else if (op == 2) {
scanf("%d%d%d", &x, &y, &z);
addedge(y, x, -z);
```
另外,OI wiki 代码另外一个错误在于判断负环时,由于建立虚拟源点,应当在 ```tot[e[i].v]>n``` 时输出 NO,而不是 ```>=n```。
by CaiZi @ 2024-02-18 15:03:33
@[ivyjiao](/user/578029)
by CaiZi @ 2024-02-18 15:04:19
@studying_father OI-wiki 上有问题的话请修改一下谢谢。
by incra @ 2024-02-18 15:05:22
@[StudyingFather](/user/22030)
by incra @ 2024-02-18 15:06:26