【传送门：BZOJ3436】
简要题意：
有n个数，这n个数存在m个关系，有三种关系：（假设a数组为n个数的值）
第一种：第i个数比第j个数至少大c（也就是a[i]-a[j]>=c）
第二种：第i个数比第j个数最多大c（也就是a[i]-a[j]<=c）
第三种：第i个数等于第j个数（也就是a[i]=a[j])
请问是否存在满足m个关系的数列，如果存在输出Yes，否则输出No
题解：
差分约束（其实挺裸的）
先来转换一下关系就得到：
第一种情况：a[j]>=a[i]-c
第二种情况：a[i]>=a[j]+c
第三种情况：a[i]>=a[j]+0 并且 a[j]>=a[i]+0（因为我们做差分的时候不能用相等来做，所以就创造两个条件来约束）
如果跑完之后发现有负环，那么说明不存在，如果没有负环则存在此数列
参考代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> using namespace std; int list[11000]; int ru[11000]; int d[11000]; bool v[11000]; struct node { int x,y,d,next; }a[11000];int len,last[11000]; void ins(int x,int y,int d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } int main() { int n,m; scanf("%d%d",&n,&m); int st=999999999,ed=0; len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int t,x,y; scanf("%d%d%d",&t,&x,&y); if(t==1) { int c; scanf("%d",&c); ins(x,y,-c); } if(t==2) { int c; scanf("%d",&c); ins(y,x,c); } if(t==3) { ins(x,y,0);ins(y,x,0); } } memset(ru,0,sizeof(ru)); memset(d,63,sizeof(d)); memset(v,false,sizeof(v)); int head=0; for(int i=1;i<=n;i++) list[++head]=i; v[list[head]]=1;d[list[head]]=0; while(head!=0) { int x=list[head];head--; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(d[y]>d[x]+a[k].d) { d[y]=d[x]+a[k].d; if(v[y]==0) { v[y]=1; head++; list[head]=y; ru[y]++; if(ru[y]==n) { printf("No "); return 0; } } } } v[x]=0; } printf("Yes "); return 0; }