POJ - 1364 巧妙构图的差分约束

题目的意思抽象出来就是有一个数列...a1,a2...an..现在给出每段的关系..若 a1+a2 > 0 , a2+a3<2 之类的..问这些条件有没有错误的出现...

构图也就是将问题转化为差分约束.... 首先用s [ i ] 来记录前 i 个的和...然后例如 a3+a4+a5 < k 的首先就可以转化为 s [ 5 ] - s [ 3 ] < k 但是差分约束是 <= 关系的..所以再次转化为:

s [ 5 ] - s [ 3 ] <= k ... 类似的.. a3+a4+a5 > k 首先就可以转化为 s [ 5 ] - s [ 3 ] > k 再转化为 s [ 3 ] - s [ 5 ] > -k 最后转化为s [ 3 ] - s [ 5 ] >= -k-1..

构图完毕后只要用Bellman-Ford来检测有无负环就可以得到结果了..

Prgoram:

#include<iostream>
using namespace std;
struct pp
{
     int x,y,k;    
}line[101];
int n,m,i;
char c; 
bool Bellman_Ford()
{
   int i,j,k,d[101]; 
   memset(d,0x7F,sizeof(d));
   d[1]=0;
   for (k=0;k<=n;k++)
     for (i=1;i<=m;i++)
       if (d[line[i].y]>d[line[i].x]+line[i].k)  
         d[line[i].y]=d[line[i].x]+line[i].k;
   for (i=1;i<=m;i++)
     if (d[line[i].y]>d[line[i].x]+line[i].k) return false;
   return true;            
}
int main()
{ 
   while (~scanf("%d",&n))
   {
       if (!n) break;
       int x,y,k;
       scanf("%d",&m);  
       for (i=1;i<=m;i++)
       {
           scanf("%d%d",&x,&y);
           y=x+y;           
           c=getchar();
           while (c==' ') c=getchar();
           if (c=='g')
           {
               getchar();
               scanf("%d",&k);    
               line[i].x=x-1; line[i].y=y; line[i].k=-k-1;       
           }else
           {
               getchar();
               scanf("%d",&k);
               line[i].x=y; line[i].y=x-1; line[i].k=k-1;
           }
       }  
       if (Bellman_Ford()) printf("lamentable kingdom\n");
       else printf("successful conspiracy\n");
   }
   return 0;   
}