本文共 1649 字，大约阅读时间需要 5 分钟。
1 /* 2 题意：一张有双方向连通和单方向连通的图，单方向的是负权值，问是否能回到过去(权值和为负) 3 Bellman_Ford：循环n-1次松弛操作，再判断是否存在负权回路(因为如果有会一直减下去) 4 注意：双方向连通要把边起点终点互换后的边加上 5 */ 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 using namespace std;16 17 const int MAXN = 6000 + 10;18 const int INF = 0x3f3f3f3f;19 int d[MAXN];20 struct NODE21 {22 int from, to, cost;23 }node[MAXN];24 25 bool Bellman_Ford(int s, int n, int m)26 {27 int x, y;28 d[s] = 0;29 for (int k=1; k<=n-1; ++k)30 {31 for (int i=1; i<=m; ++i)32 {33 NODE e = node[i];34 d[e.to] = min (d[e.to], d[e.from] + e.cost);35 }36 }37 38 for (int i=1; i<=m; ++i)39 {40 NODE e = node[i];41 if (d[e.to] > d[e.from] + e.cost) return false;42 }43 44 return true;45 }46 47 void work(int n, int m)48 {49 bool flag = false;50 flag = Bellman_Ford (1, n, m);51 52 (!flag) ? puts ("YES") : puts ("NO");53 }54 55 int main(void) //POJ 3259 Wormholes56 {57 //freopen ("B.in", "r", stdin);58 59 int N, M, W;60 int t;61 scanf ("%d", &t);62 while (t--)63 {64 scanf ("%d%d%d", &N, &M, &W);65 for (int i=1; i<=N; ++i) d[i] = INF;66 67 int x, y, z;68 for (int i=1; i<=2*M; ++i)69 {70 scanf ("%d%d%d", &x, &y, &z);71 node[i].from = x; node[i].to = y; node[i].cost = z;72 node[++i].from = y; node[i].to = x; node[i].cost = z;73 }74 75 for (int i=2*M+1; i<=2*M+W; ++i)76 {77 scanf ("%d%d%d", &x, &y, &z);78 node[i].from = x; node[i].to = y; node[i].cost = -z;79 }80 81 work (N, 2*M+W);82 }83 84 return 0;85 }
转载于:https://www.cnblogs.com/Running-Time/p/4372560.html