POJ 1364 King （差分約束）

題目大意：

有一個序列S[1], S[2],S[3],S[4].....

讀入si，ni，oi，ki，

oi表示大於和小於，如果是gt，則是大於，如果是lt，則是小於

輸入表示 S[si]到S[si+ni]的和 大於/小於 ki

即：

T[si+ni]-T[si-1]>ki(oi為gt) 等價於：T[si-1]-T[si+ni]<-ki

T[si+ni]-T[si-1]<ki(oi為lt)

典型的差分約束，但是裡面有一個小技巧，差分約束只能處理小於等於和大於等於的情況，在本題中，因為序列都是整數，可以轉化為：

T[si-1]-T[si+ni]<-ki-1(oi為gt)

T[si+ni]-T[si-1]<=ki-1(oi為lt)

AC代碼如下：

[cpp]
/*POJ1364
作者：陳佳潤
2013-05-10*/ 
#include<iostream>  
using namespace std; 
#include<stdio.h>  
struct Edge{ 
    int u,v; 
    int w; 
}edge[105];//存放邊的結構體數組  
 
int dis[105];//到源點距離表  
int m;//邊的數目  
int n;//點的個數  
 
void createEdge(int num,int u,int v,int w){ 
    edge[num].u=u; 
    edge[num].v=v; 
    edge[num].w=w; 
} 
 
bool Bellman(){ 
    int i,k; 
    for(i=0;i<n;i++)//初始化  
        dis[i]=0; 
    //Bellman 算法  
    for(i=0;i<n;i++){//Bellman 算法  
        for(k=0;k<m;k++){ 
            if(dis[edge[k].v]>edge[k].w+dis[edge[k].u]){ 
                dis[edge[k].v]=edge[k].w+dis[edge[k].u]; 
            } 
        } 
    } 
    //檢查負權回路  
    for(k=0;k<m;k++){ 
        if(dis[edge[k].v]>edge[k].w+dis[edge[k].u]){ 
            return false; 
        } 
    } 
    return true; 
} 
 
int main(){ 
    char oi[3]; 
    int si,ni,ki,i; 
    while(cin>>n,n){ 
        cin>>m; 
        for(i=0;i<m;i++){//讀入和建圖  
            scanf("%d%d%s%d",&si,&ni,oi,&ki); 
            if(oi[0]=='g') 
                createEdge(i,si+ni,si-1,-ki-1); 
            else 
                createEdge(i,si-1,si+ni,ki-1);   
        } 
         
        if(!Bellman()) 
            printf("successful conspiracy\n"); 
        else 
            printf("lamentable kingdom\n"); 
    } 
    return 0; 
} 

/*POJ1364
作者：陳佳潤
2013-05-10*/
#include<iostream>
using namespace std;
#include<stdio.h>
struct Edge{
 int u,v;
 int w;
}edge[105];//存放邊的結構體數組

int dis[105];//到源點距離表
int m;//邊的數目
int n;//點的個數

void createEdge(int num,int u,int v,int w){
 edge[num].u=u;
 edge[num].v=v;
 edge[num].w=w;
}

bool Bellman(){
 int i,k;
 for(i=0;i<n;i++)//初始化
  dis[i]=0;
 //Bellman 算法
 for(i=0;i<n;i++){//Bellman 算法
  for(k=0;k<m;k++){
   if(dis[edge[k].v]>edge[k].w+dis[edge[k].u]){
    dis[edge[k].v]=edge[k].w+dis[edge[k].u];
   }
  }
 }
 //檢查負權回路
 for(k=0;k<m;k++){
  if(dis[edge[k].v]>edge[k].w+dis[edge[k].u]){
   return false;
  }
 }
 return true;
}

int main(){
 char oi[3];
 int si,ni,ki,i;
 while(cin>>n,n){
  cin>>m;
  for(i=0;i<m;i++){//讀入和建圖
   scanf("%d%d%s%d",&si,&ni,oi,&ki);
   if(oi[0]=='g')
    createEdge(i,si+ni,si-1,-ki-1);
   else
    createEdge(i,si-1,si+ni,ki-1); 
  }
  
  if(!Bellman())
   printf("successful conspiracy\n");
        else
            printf("lamentable kingdom\n");
 }
 return 0;
}