对于第三个条件也就是相等,本应该这样写
add(a, b, 0); //a>=b a>=0+b
add(b, a, 0);
然而我突发奇想搞了个这样的写法
add(0, a, b);
add(0, b, a);
神奇的是这样也能过!所以是数据太水还是下面的方法就是对的,这个……请求帮助,万分感谢!
最后附上下文(我是用最长路做的)
#include <iostream>
#include <cstring>
using namespace std;
const int N = 5005, M = 5005 * 5, INF = 0x3f3f3f3f;
int n, m, idx;
int h[N], e[M], w[M], ne[M];
int q[N], cnt[N], dist[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 ++ ;
return;
}
bool spfa()
{
memset(dist, -0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
int hh = 0, tt = 1;
q[0] = 0;
dist[0] = 0;
st[0] = 1;
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = 0;
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] = cnt[t] + 1;
if (cnt[j] >= n) return 0;
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = 1;
}
}
}
}
return 1;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- )
{
int x;
cin >> x;
if (x == 1)
{
int a, b, c;
cin >> a >> b >> c;
add(b, a, c); //a-b>=c a>=b+c b--c-->a 最长路
}
else if (x == 2)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, -c); //a-b<=c b>=a-c
}
else
{
int a, b;
cin >> a >> b;
//add(a, b, 0); //a>=b a>=0+b
//add(b, a, 0);
add(0, a, b);
add(0, b, a);
}
}
for (int i = 1; i <= n; i ++ ) add(0, i, 0);
if (!spfa()) cout << "No" << endl;
else cout << "Yes" << endl;
return 0;
}