【图论】差分约束

一.情景导入

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;
}