POJ1364

4 2
1 2 gt 0
2 2 lt 2
if(s[0]=='g') S3-S0>0 S3-S0>=1 S0-S3<=-1
if(s[0]=='l') S4-S1<2 S4-S1<=1
因为图有可能不连通，所以我们添加一个超级源点 n+1 ，然后建n+1到各个顶点的边，权值为0
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 using namespace std;
 8 #define inf 9999999
 9 #define N 105
10 #define M 20000
11 int dis[N],vis[N],head[N],in[N];
12 int size , n ,m ;
13 struct Edge
14 {
15     int v,w,next;
16     Edge(){}
17     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
18 }edge[M];
19 
20 void Init()
21 {
22     size = 0;
23     memset(head,-1,sizeof(head));
24 }
25 
26 void InsertEdge(int u,int v,int w)
27 {
28     edge[size] = Edge(v,w,head[u]);
29     head[u] = size++;
30 }
31 
32 bool SPFA()
33 {
34     for(int i=0; i<=n; i++) //建超级源点到其他各点的边 ，保证图联通 
35     InsertEdge(n+1,i,0);
36     for(int i=0; i<=n+1; i++)
37     {
38         dis[i] = inf;
39         vis[i] = 0;
40         in[i] = 0;
41     }
42     queue<int> Q;
43     while(!Q.empty()) Q.pop();
44     vis[n+1] = 1 ; dis[n+1] = 0; in[n+1] = 1;

45     Q.push(n+1);
46     while(!Q.empty())
47     {
48         int u = Q.front();
49         Q.pop();
50         vis[u] = 0;
51         for(int i=head[u]; i!=-1 ; i = edge[i].next)
52         {
53             int v = edge[i].v;
54             if(dis[v] > dis[u] + edge[i].w)
55             {
56                 dis[v] = dis[u] + edge[i].w;
57                 if(!vis[v])
58                 {
59                     vis[v] = 1;
60                     in[v]++;
61                     if(in[v]>(n+2)) return 0; //因为总共n+2个点， 
62                     Q.push(v);
63                 }
64             }
65         }
66     }
67     return 1;
68 }
69 
70 int main()
71 {
72     while(scanf("%d",&n)!=EOF)
73     {
74         if(n==0) break;
75         scanf("%d",&m);
76         Init();
77         int u,v,w;
78         char s[5];
79         while(m--)
80         {
81             scanf("%d%d%s%d",&u,&v,s,&w);
82             if(s[0]=='g') InsertEdge(u+v,u-1,-(w+1));
83             if(s[0]=='l') InsertEdge(u-1,u+v,(w-1));
84         }
85         if(SPFA()) printf("lamentable kingdom
");
86         else printf("successful conspiracy
");
87     }
88     return 0;
89 }
View Code