个人认为能解决很多个不等式是否存在解或者最小解的问题
先说个简单题：poj3159
题意：n个人，m个条件，输入a,b,k代表b比a最多多k个糖
问：第n个人最多有多少糖
对于每个条件都得出一个不等式 b-a<=k
若输入中有
a b x
b c y
a c z
那么c最多比a多min(x+y,z)
因此从1到n的最短路中dis[n]-dis[1]就是最终答案
对于hdu6252
题意：输入n,m,x。表示n个地方，有两个人从1走到n，第二个人先走x分钟，m次询问
每次询问输出a,b,c,d如果 a==b表示第一个人在a，否则表示第一个人在a~b的路上,如果 c==d表示第二个人在c，否则表示第二个人在c~d的路上。
问:是否存在一个图（图一定是顺次连接1~n）满足条件，若存在输出每段的长度
输入中a==b而且c==d说明 c-b==x同时也说明c-b>=x c-b<=x
如果a!=b或者c!=d说明c-b<x也就是c-b<=x-1。d-a>x也就是d-a>=x+1
这里用大于的是负的边权，小于是正的边权，那么我们需要判断是否有负环即可，只要没有负环就是有解
为了有解，我们要让值都尽可能大
对于a-b>=v，-(a-b)<=-v,为了使值更大，所以a到b的边为-v
对于a-b<=v，为了使值更大，所以a到b的边为-v
最后跑个bellman判负环即可（套了spfa表示慢了700ms)
其实若大于用正边权，小于用负边权也可以，只需要判断是否有正环即可
若有解只需要dis[i]-dis[i-1]即可，由于正向是负数，所以需要加个负号
#include<stdio.h> #include<string.h> #define MAXN 2005 #define INF 0x3f3f3f3f #define rep(i,j,k) for(int i=j;i<=k;++i) int dist[MAXN]; struct s { int x,y,v; } edge[MAXN*10]; int tot; void add(int x,int y,int v) { edge[++tot].x=x; edge[tot].y=y; edge[tot].v=v; } int n,m; bool Bellman(int st) { rep(i,1,n) dist[i]=INF; dist[st]=0; rep(i,1,n-1) { rep(j,1,tot) { if(dist[edge[j].y]>dist[edge[j].x]+edge[j].v) dist[edge[j].y]=dist[edge[j].x]+edge[j].v; } } rep(j,1,tot) { if(dist[edge[j].y]>dist[edge[j].x]+edge[j].v) return false; } return true; } int main() { int t,kk=1; scanf("%d",&t); while(t--) { int x; scanf("%d %d %d",&n,&m,&x); tot=0; rep(i,2,n) add(i-1,i,-1); int a,b,c,d; rep(i,1,m) { scanf("%d %d %d %d",&a,&b,&c,&d); if(a==b&&c==d) { add(c,a,x);///a-c距离小于等于x add(a,c,-x);///a-c距离大于等于x } else { add(c,b,x-1);///b-c距离小于x add(a,d,-(x+1));///a-d距离大于等于x+1 } } printf("Case #%d: ",kk++); if(Bellman(1)) { rep(i,2,n) printf("%d%c",dist[i-1]-dist[i],i==n?' ':' '); } else printf("IMPOSSIBLE "); } }