poj 1364 King（差分约束）

题意（真坑）：傻国王只会求和，以及比较大小。阴谋家们想推翻他，于是想坑他，上交了一串长度为n的序列a[1],a[2]...a[n]，国王作出m条形如(a[si]+a[si+1]+...+a[si+ni])>k（或<k）的批示，结果发现批错了，问是否存在一个满足不等式组的序列a[1]...a[n]，好让国王借口自己看错了。

因为是求是否存在，即判环，没有要求最大还是最小，所以最长路、最短路都可以解决。

注意:

1、总点数，若不加源点而采用把所有点入队，总点数==n+1；否则，总点数==n+2。这影响到cnt[]>n还是cnt[]>(n+1)。

2、差分约束求解的是>=以及<=的问题，这里的>(或<)可以变化一下，>k等价于>=(k+1)。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 #define rep(i,a,b) for(int i=a;i<=b;i++)
 6 #define clr(a,m) memset(a,m,sizeof(a))
 7 using namespace std;
 8 
 9 const int MAXN=111;//经尝试，MAXN==49就能过，poj的数据真水
10 const int INF =MAXN;
11 
12 struct Edge{
13     int v,c,next;
14     Edge(){}
15     Edge(int _v,int _c,int _next):v(_v),c(_c),next(_next){}
16 }edge[MAXN<<2];
17 
18 int head[MAXN],tol;
19 int d[MAXN],inq[MAXN],cnt[MAXN];
20 
21 void init()
22 {
23     tol=0;
24     clr(head,-1);
25 }
26 
27 void add(int u,int v,int c)
28 {
29     edge[tol]=Edge(v,c,head[u]);
30     head[u]=tol++;
31 }
32 
33 int SPFA(int n)
34 {
35     queue<int>q;
36     clr(cnt,0);
37     rep(i,0,n){
38         d[i]=0;
39         inq[i]=true;
40         q.push(i);
41     }
42     inq[0]=true;
43     while(!q.empty())
44     {
45         int u=q.front();q.pop();
46         inq[u]=false;
47         for(int i=head[u];i!=-1;i=edge[i].next)
48         {
49             int v=edge[i].v;
50             int c=edge[i].c;
51             if(d[v]<d[u]+c){
52                 d[v]=d[u]+c;
53                 if(!inq[v]){
54                     q.push(v);
55                     if(++cnt[v]>n)
56                         return true;
57                     inq[v]=true;
58                 }
59             }
60         }
61     }
62     return false;
63 }
64 
65 int main()
66 {
67     int n,m;
68     int u,v,c;
69     char op[5];
70     while(~scanf("%d",&n))
71     {
72         if(!n)
73             return 0;
74         scanf("%d",&m);
75         init();
76         rep(i,1,m){
77             scanf("%d%d%s%d",&u,&v,op,&c);
78             v+=u;u--;
79             if(op[0]=='g')
80                 add(u,v,c+1);
81             else
82                 add(v,u,-c+1);
83         }
84         if(SPFA(n))
85             printf("successful conspiracy
");
86         else
87             printf("lamentable kingdom
");
88     }
89     return 0;
90 }

View Code