题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2330
差分约束。
在最短路中有d[v]<=d[u]+e[j].c =>d[v]-d[u]<=e[j].c ,把不等式转成这个形式。
1. 如果要求最大值想办法把每个不等式变为标准x-y<=k的形式,然后建立一条从y到x权值为k的边,变得时候注意x-y<k =>x-y<=k-1
如果要求最小值的话,变为x-y>=k的标准形式，然后建立一条从y到x的k边，求出最长路径即可
2.如果权值为正，用dj，spfa，bellman都可以，如果为负不能用dj，并且需要判断是否有负环，有的话就不存在
#include<cstring> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstdio> #include<cmath> #include<queue> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 100500 #define ll long long using namespace std; struct data{int obj,pre,c; }e[maxn*4]; ll ans; int n,m,tot; int c[maxn],head[maxn],vis[maxn]; ll dis[maxn]; ll read(){ ll x=0,f=1; char ch=getchar(); while (!isdigit(ch)) { if (ch==‘-‘) f=-1; ch=getchar(); } while (isdigit(ch)){ x=x*10+ch-‘0‘; ch=getchar(); } return x*f; } void insert(int x,int y,int z){ e[++tot].obj=y; e[tot].pre=head[x]; e[tot].c=z; head[x]=tot; } bool spfa(){ clr(c,0); clr(dis,0); clr(vis,0); c[0]=1; queue<int> q; q.push(0); while (!q.empty()){ int u=q.front(); q.pop(); vis[u]=1; for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; if (dis[v]<dis[u]+e[j].c){ if (++c[v]>=n) return 0; dis[v]=dis[u]+e[j].c; if (vis[v]==0) vis[v]=1,q.push(v); } } vis[u]=0; } return 1; } int main(){ n=read(); m=read(); rep(i,1,m){ int op=read(),x=read(),y=read(); if (op==1) insert(x,y,0),insert(y,x,0); if (op==2) {if (x==y) {puts("-1"); return 0;} insert(x,y,1);} if (op==3) insert(y,x,0); if (op==4) {if (x==y) {puts("-1"); return 0;} insert(y,x,1);} if (op==5) insert(x,y,0); } down(i,n,1) insert(0,i,1); if (!spfa()) puts("-1"); else { rep(i,1,n) ans+=dis[i]; printf("%lld\n",ans); } return 0; }
原文：http://www.cnblogs.com/ctlchild/p/5031131.html