poj1364King

WA了n次啊一个a和b写反了。。无语了

题意好难懂 aSi + aSi+1 + ... + aSi+ni < ki or aSi + aSi+1 + ... + aSi+ni > ki 为了得到差分约束不等式令sum[ni] = asi+asi+1+。。+asi+ni

上式就可变为 sum[ni+si]-sum[si-1]<=ki+1(sum[si-1]-sum[ni+si]>=-ki-1) or sum[ni+si]-sum[si-1]>=ki-1

bellford 判负环即判断这些不等式能不能成立

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stdlib.h>
 5 using namespace std;
 6 int n,m,g;
 7 struct node
 8 {
 9     int u,v,w;
10 }e[210];
11 int dis[110];
12 int bellford()
13 {
14     int i,j,flag=0;
15     memset(dis,0,sizeof(dis));
16     for(i = 1 ; i <= n+1 ; i++)
17     {
18         flag = 0;
19         for(j = 1; j <= g; j++)
20         {
21             if(dis[e[j].v]>dis[e[j].u]+e[j].w)
22             {
23                 dis[e[j].v] = dis[e[j].u]+e[j].w;
24                 flag = 1;
25             }
26         }
27         if(!flag)
28         break;
29     }
30     if(flag)
31     return 0;
32     else
33     return 1;
34 }
35 int main()
36 {
37     int i,j,k,a,b,c;
38     char s[10];
39     while(cin>>n)
40     {
41         if(!n)
42         break;
43         cin>>m;
44         g=0;
45         for(i = 1; i <= m ; i++)
46         {
47             scanf("%d%d%s%d",&a,&b,s,&k);
48             if(s[0]=='g')
49             {
50                 g++;
51                 e[g].u = a+b;
52                 e[g].v = a-1;
53                 e[g].w = -1-k;
54             }
55             else
56             {
57                 g++;
58                 e[g].u = a-1;
59                 e[g].v = a+b;
60                 e[g].w = k-1;
61             }
62         }
63         if(!bellford())
64         {
65             puts("successful conspiracy");
66         }
67         else
68             puts("lamentable kingdom");
69     }
70     return 0;
71 }