题目类型 Bellman-Ford算法的运用
题目意思
给出 n (1 <= n <= 500) 个点, m (1 <= m <= 2500) 条双向边 和 w (1 <= w <= 200) 条单向边 其中双向边的边权为正 单向边边权为负
问能否从某个点出发最终回到这个点 经过的边的权值加起来是负的
解题方法
和poj1860相似 看是否存在负环即可
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 6000;
const int INF = 1<<29;
struct P {
int u, v, t;
}E[maxn];
int d[maxn];
int main() {
freopen("in", "r", stdin);
int t;
scanf("%d", &t);
while(t--) {
int n, m, w;
int ne = 0;
scanf("%d%d%d", &n, &m, &w);
for( int i=0; i<m; i++ ) {
int u, v, t;
scanf("%d%d%d", &u, &v, &t);
E[ne].u = u; E[ne].v = v; E[ne++].t = t;
E[ne].u = v; E[ne].v = u; E[ne++].t = t;
}
for( int i=0; i<w; i++ ) {
int u, v, t;
scanf("%d%d%d", &u, &v, &t);
E[ne].u = u; E[ne].v = v; E[ne++].t = -t;
}
for( int i=1; i<=n; i++ ) d[i] = INF;
d[1] = 0;
for( int i=0; i<n; i++ ) {
bool flag = false;
for( int j=0; j<ne; j++ ) {
int u = E[j].u, v = E[j].v;
if(d[v] > d[u] + E[j].t) {
d[v] = d[u] + E[j].t;
flag = true;
}
}
if(i == n-1) { // 松弛n-1次后还可以松弛说明存在负环
if(flag) printf("YES\n");
else printf("NO\n");
}
}
}
return 0;
}