一道较简单的差分约束题，但这题我忽略了两个问题，以致wrong了13次啊。。首先要注意的是，此题中|V|=n+1,所以外层循环的循环次数为n，而不是想当然的认为是n-1；第二点就是本题中的约束条件不是大于就是小于，不包含等于，所以不能直接按照已知条件建边。
发现这两个错误后，总算A掉了啊啊……
/*
此题是一道差分约束问题，但有个细节需要注意下，就是
此处的约束条件是'<'或'>'，不包含'=’,所以不能直接根据题意建边，
注意到集合S中的元素为整数，所以可以对原始约束条件做一个处理，
比如，已知s3-s0>1,我们可以写成s3-s0>=2，这样该题就完全成为了一个
差分约束了。
*/
#include
#includeusing namespace std;
struct
{
int u,v,w;
}e[105];
intd[105];
int n,m;
bool relax(int u,int v,int w)
{
if(d[u]+w"
{
e[i].u=b;
e[i].v=a-1;
e[i].w=-c-1;
}
else//"<"
{
e[i].u=a-1;
e[i].v=b;
e[i].w=c-1;
}
}
if(Bellman_Ford())
printf("lamentable kingdom\n");
else
printf("successful conspiracy\n");
}
return 0;
}
【poj 1364 King 差分约束】
