题意：
n个数，知道m条关系：a-b≥c、a-b≤c或a==b。问是否存在满足所有关系的情况。n≤10000，m≤10000。
题解：
差分约束。因为只要求是否满足，因此最短路最长路都可以。不过要注意如果是用spfa的bfs写法，每个点都必须作为源点判一次负环，因为图可能不连通。正因为如此，虽说加了SLF的bfs写法spfa能卡过，但比dfs写法慢不只10倍。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 10010
#define INF 0x3fffffff
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
} struct e{int t,w,n;}; e es[maxn*]; int g[maxn],ess;
void pe(int f,int t,int w){es[++ess]=(e){t,w,g[f]}; g[f]=ess;}
int n,m,cnt[maxn],d[maxn]; bool inq[maxn]; deque<int>q;
ll spfa(int s){
q.clear(); memset(inq,,sizeof(inq)); memset(cnt,,sizeof(cnt));
q.push_back(s); inq[s]=; d[s]=; cnt[s]=;
while(!q.empty()){
int x=q.front(); q.pop_front(); inq[x]=;
for(int i=g[x];i;i=es[i].n)if(d[es[i].t]>d[x]+es[i].w){
d[es[i].t]=d[x]+es[i].w;
if(!inq[es[i].t]){
if(!q.empty()&&d[es[i].t]<d[q.front()])q.push_front(es[i].t);else q.push_back(es[i].t);
inq[es[i].t]=; cnt[es[i].t]++; if(cnt[es[i].t]>=n)return ;
}
}
}
return ;
}
int main(){
n=read(); m=read();
inc(i,,m){
int opt=read(),a,b,c;
if(opt==)a=read(),b=read(),c=read(),pe(a,b,-c);
if(opt==)a=read(),b=read(),c=read(),pe(b,a,c);
if(opt==)a=read(),b=read(),pe(b,a,),pe(a,b,);
}
inc(i,,n)if(!spfa(i)){puts("No"); return ;} puts("Yes"); return ;
}
20161018