设s[i] 表示a1 + a2 + ... + a(i-1)的和
给我们n个点，m条约束
如果是a b gt c 那么表示 s[a+b+1] - s[a] > c ---> s[a] -s[a+b+1] <-c <=-c-1 --> s[a] <= s[a+b+1] + (-c-1)
如果是a b lt c 那么表示 s[a+b+1] - s[a] < c ---> s[a+b+1] - s[a] <= c - 1 --> s[a+b+1] <= s[a] + (c-1)
题目要问我们是不是所有变量都满足约束条件，如果满足输出lamentable kingdom， 如果不满足，输出successful conspiracy
满不满足约束条件， 即图存不存在负权回路。
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 #pragma warning(disable:4996) 15 typedef long long LL; 16 const int INF = 1<<30; 17 /* 18 s[a+b+1] - s[a] >c --> s[a] - s[a+b+1] < -c <= -c-1 19 s[a+b+1] - s[a] <c --> s[a+b+1] -s[a] < c <= c-1 20 不连通要我们求环 21 */ 22 struct Edge 23 { 24 int from,to,dist; 25 }es[100+10]; 26 int dist[100+10]; 27 bool bellman_ford(int n, int m) 28 { 29 //因为是求存不存在负权回路，那么只要初始化为0，更新n遍之后，如果还能再更新，那么就存在 30 for(int i=1; i<=n; ++i) 31 dist[i] = 0; 32 for(int i=1; i<=n; ++i)//n+1个点，所以要更新n遍 33 { 34 for(int j=0; j<m; ++j) 35 { 36 Edge &e = es[j]; 37 //因为图是不连通的，所以如果置为INF的时候，不能在这里加这个条件 38 if(/*dist[e.from]!=INF &&*/ dist[e.to] > dist[e.from] + e.dist) 39 dist[e.to] = dist[e.from] + e.dist; 40 } 41 } 42 for(int j=0; j<m; ++j) 43 { 44 Edge &e = es[j]; 45 if(dist[e.to] > dist[e.from] + e.dist) 46 return false; 47 } 48 return true; 49 } 50 int main() 51 { 52 53 int n,m,a,b,c,i; 54 char str[3]; 55 while(scanf("%d",&n),n) 56 { 57 scanf("%d",&m); 58 for(i=0; i<m; ++i) 59 { 60 scanf("%d%d%s%d",&a,&b,str,&c); 61 if(str[0]=='g') 62 { 63 es[i].from = a + b + 1; 64 es[i].to = a; 65 es[i].dist = -c - 1; 66 } 67 else 68 { 69 es[i].from = a; 70 es[i].to = a + b +1; 71 es[i].dist = c-1; 72 } 73 } 74 bool ret = bellman_ford(n,m); 75 if(ret) 76 puts("lamentable kingdom"); 77 else 78 puts("successful conspiracy"); 79 } 80 return 0; 81 }