poj 1364 King

题意：已知一个序列a[1], a[2], ......, a[n]，给出它的若干子序列以及对该子序列的约束条件，例如a[si], a[si+1], a[si+2], ......, a[si+ni]，且a[si]＋a[si+1]＋a[si+2]＋......＋a[si+ni] < or > ki。

转化：a[a] + a[a+1] + …… + a[b] < c 可以转化成前n项和sum[b] - sum[a - 1] < c，为了能用Bellman_Ford,即将< 转化成 <= ，sum[b] - sum[a - 1] <= c - 1。

注意：1，松弛时一共有N+1次，因为这个N与bellman——ford里面的n不是同一个，在虚拟加入了一个x0后，应该有N+1个顶点。

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 struct Edge
 9 {
10     int s,e;
11     int val;
12 }edge[210];
13 
14 int pe;
15 int N,M;
16 int dis[110];
17 
18 bool bellman_ford()
19 {
20     bool sign;
21 
22     for(int j=0;j<N+1;j++)
23     {
24         sign=false;
25         for(int i=0;i<pe;i++)
26             if(dis[edge[i].e] > dis[edge[i].s] + edge[i].val)
27             {
28                 dis[edge[i].e] = dis[edge[i].s] + edge[i].val;
29                 sign=true;
30             }
31         if(!sign)
32             break;
33     }
34     if(sign)
35         return false;//存在负环
36     else
37         return true;
38 }
39 
40 int main()
41 {
42     while(scanf("%d",&N) && N)
43     {
44         scanf("%d",&M);
45         memset(dis,0,sizeof(dis));//虚拟出一个x0，xi-x0<=0
46         pe=0;
47 
48         char op[3];
49         int a,b,x;
50 
51         for(int i=0;i<M;i++)
52         {
53             getchar();
54             scanf("%d%d%s%d",&a,&b,&op,&x);
55             if(op[0]=='l')
56             {
57                 edge[pe].s=a-1;
58                 edge[pe].e=a+b;
59                 edge[pe++].val=x-1;
60             }
61             else
62             {
63                 edge[pe].s=a+b;
64                 edge[pe].e=a-1;
65                 edge[pe++].val=-x-1;
66             }
67         }
68         if(bellman_ford())
69             puts("lamentable kingdom");
70         else
71             puts("successful conspiracy");
72     }
73     return 0;
74 }