第一次看这个题目，完全不知道怎么做，看起来又像是可以建个图进行搜索，但题目条件就给了你几个不等式，这是怎么个做法。。。之后google了下才知道还有个差分约束这样的东西，能够把不等式化成图，要求某个点在满足所有不等式的情况下的最大取值，只需对建好的图进行一次最短路即可
不过要使得a b 点满足这样 a<=b+k这种不等式，还得对题目所给的不等式进行下改装
原不等式无非就是 输入个 si ni,使得存在 A(si)+...A(si+ni)<k 或者 >k，我们新定义一个s[],s[i]代表从1 到 i的所有的点的和，这样，原不等式就会变成 s[si+ni]-s[si-1]>=k+1 或者 小于=k-1，进行下移项，即可变成差分约束不等式的形式，这样每个点的含义就是 对应的s[i]。
此外注意添加一个超级原点 N+1，跟所有点进行下连通，保证图的连通性。
其实题目还有个难点就是，他求是否能满足着m个不等式，如果不满足，意味着有相互冲突的不等式，也就是某个点值既可能正也可能负，也就是说图上存在负环。。。。这个转换确实比较难推敲，尤其是像我这种对图论题目还只是入门的菜鸟。
因此，建好图后，只需用SPFA遍历一下，判断有无负环即可。
此外，还有个疑惑，就是差分约束一定要有等于吗？就像上面的式子，如果不是为了满足=的条件，就不必用k+1和k-1来代替原来的k了。。。这个还有待考证
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define N 250 using namespace std; int u[N],v[N],w[N],nt[N],ft[N/2],d[N/2],num[N/2],vis[N/2]; int n,m,cnt,flag; void addedge(int a,int b,int c) { u[cnt]=a; v[cnt]=b; w[cnt]=c; nt[cnt]=ft[a]; ft[a]=cnt++; } void spfa() { int i,j; for (i=0;i<=n;i++) d[i]=1<<30; memset(num,0,sizeof num); memset(vis,0,sizeof vis); flag=1; d[n+1]=0; queue <int> q; q.push(n+1); vis[n+1]=1; while (!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; num[x]++; if (num[x]>n) { flag=0; return; } for (i=ft[x];i>=0;i=nt[i]) { int nx=v[i]; if (d[nx]>d[x]+w[i]) { d[nx]=d[x]+w[i]; if (!vis[nx]) { q.push(nx); vis[nx]=1; } } } } } int main() { int i,j; char ch[3]; while (scanf("%d",&n)) { if (!n) break; cnt=0; scanf("%d",&m); int a,b,k,si,ni; memset(ft,-1,sizeof ft); for (i=1;i<=m;i++) { scanf("%d%d%s%d",&si,&ni,ch,&k); if (ch[0]=='g') { addedge(si+ni,si-1,(-k-1));//用差分约束不等式建图，下同 } else { addedge(si-1,si+ni,k-1); } } for (i=1;i<=n;i++) //将n+1作为超级原点进行连通。 addedge(n+1,i,0); spfa(); if (flag) { puts("lamentable kingdom"); } else puts("successful conspiracy"); } return 0; }