题目大意:
有一个序列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]
典型的差分约束,但是里面有一个小技巧,差分约束只能处理小于等于和大于等于的情况,在本题中,因为序列都是整数,可以转化为:
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
using namespace std;
#include
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 dis[i]=0;
//Bellman 算法
for(i=0;i for(k=0;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 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 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
using namespace std;
#include
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 dis[i]=0;
//Bellman 算法
for(i=0;i for(k=0;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 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 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;
}