問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3259思路:
這題的描述挺有意思，通過某些路徑可以回到過去之類，其實就是求是否存在負權回路的問題
Bellman-Ford算法的典型應用
一個問題是，Bellman-Ford用于判斷從某個源點可達的負權回路，而這里求的是整個圖，而且也沒有說明該圖一定是connected的
解決上述問題的一個方法就是添加一個頂點，然后從該新頂點到每個其他頂點添加一條權值為0的邊
代碼:
1 /* Bellman-Ford algorithm */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_N 501
6 #define MAX_M 2501
7 #define MAX_W 201
8 #define INF 0x7FFFFFFF
9 struct Edge {
10 int from, to;
11 int cost;
12 } edges[MAX_M*2+MAX_W+MAX_N];
13 int d[MAX_N];
14 int n, total;
15
16 void
17 init()
18 {
19 int i, m, w, f, t, c;
20 scanf("%d %d %d", &n, &m, &w);
21 total = 0; /* the number of edges */
22 for(i=0; i<m; i++) {
23 scanf("%d %d %d", &f, &t, &c);
24 edges[total].from = f;
25 edges[total].to = t;
26 edges[total++].cost = c;
27 edges[total].from = t;
28 edges[total].to = f;
29 edges[total++].cost = c;
30 }
31 for(i=0; i<w; i++) {
32 scanf("%d %d %d", &f, &t, &c);
33 edges[total].from = f;
34 edges[total].to = t;
35 edges[total++].cost = c*(-1);
36 }
37 /* in order to keep connectivity, add one vertex: '0' */
38 for(i=1; i<=n; i++) {
39 edges[total].from = 0;
40 edges[total].to = i;
41 edges[total++].cost = 0;
42 }
43 }
44
45 void
46 relax(struct Edge *e)
47 {
48 if(d[e->from] == INF)
49 return;
50 if(d[e->to] > d[e->from]+e->cost)
51 d[e->to] = d[e->from]+e->cost;
52 }
53
54 int
55 bellman_ford()
56 {
57 int i, j;
58 for(i=0; i<=n; i++)
59 d[i] = INF;
60 d[0] = 0;
61 for(i=0; i<n; i++) /* n+1 vertices */
62 for(j=0; j<total; j++) /* 2*m+w+n edges */
63 relax(edges+j);
64 for(j=0; j<total; j++) {
65 if(d[edges[j].to] > d[edges[j].from]+edges[j].cost)
66 return 0;
67 }
68 return 1;
69 }
70
71 int
72 main(int argc, char **argv)
73 {
74 int F;
75 scanf("%d", &F);
76 while(F--) {
77 init();
78 printf("%s\n", bellman_ford()==1?"NO":"YES");
79 }
80 }