【图论】差分约束
一.情景导入
x1-x0<=9 ; x2-x0<=14 ; x3-x0<=15 ; x2-x1<=10 ; x3-x2<=9;
求x3-x0的最大值；
二.数学解法
联立式子2和5，可得x3-x0<=23;但式子3可得x3-x0<=15。所以最大值为15；
三.图论
但式子多了我们就不好解了，或者说在计算机中怎么解呢？
我们可以想到，不妨把式子转为图的形式。我们令x0-->x1的边表示为x1-x0<=边权值。
则以上式子可以画图为：
这边，x3-x0可以为：（即x3-x0<=15）
也可以为：（即x3-x0<=28）
还可以为 :（即x3-x0<=25）
所以我们取最短路径即可！
四.差分约束
这个即是差分约束的模型
注意：
当出现负环的情况，我们可知，式子是无解的！（所以要用spfa算法判断负环）
当要求的两个点没有联通时，可知这两个式子没有约束！所有解都有可能！
五.例题：
3169 -- 布局 (poj.org)
样例输入：
4 2 1 1 3 10 2 4 20 2 3 3样例输出：
27
六.参考代码
/*
4 2 1
1 3 10
2 4 20
2 3 327
*/#include<bits/stdc++.h>
#define maxn 20005
#define maxm 1001
#define inf 0x7fffffff
using namespace std;
int cnt=0;
struct Edge{int u,v,w,next;
}edge[maxn];
int head[maxm];
void add(int u,int v,int w){edge[++cnt]=(Edge){u,v,w,head[u]}; head[u]=cnt;
}
int n,x,y;
bool vis[maxm];
int in[maxm],dis[maxn]; //判断负环
//基础，不会的话看我以前的博客
int spfa(int x){queue<int> q;for(int i=1;i<=n;i++){dis[i]=inf;}dis[x]=0;in[x]++;q.push(x);while(!q.empty()){int u=q.front(); q.pop();vis[u]=0;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v,w=edge[i].w;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;if(!vis[v]){vis[v]=1;q.push(v);in[v]++;if(in[v]>n) return -1; //负环 }}} }if(dis[n]==inf) return -2; //无限制return dis[n];
}
int main(){cin>>n>>x>>y;int u,v,w;for(int i=1;i<=x;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w);}for(int i=1;i<=y;i++){scanf("%d%d%d",&u,&v,&w);add(v,u,-w);}//是站成一条直线 for(int i=1;i<n;i++){add(i+1,i,-1);}cout<<spfa(1); return 0;
}