【图论】差分约束-Toy模板网

这篇具有很好参考价值的文章主要介绍了【图论】差分约束。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.情景导入

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<=边权值。

则以上式子可以画图为：

【图论】差分约束,图论,图论,算法,c++

这边，x3-x0可以为：（即x3-x0<=15）

【图论】差分约束,图论,图论,算法,c++

也可以为：（即x3-x0<=28）

【图论】差分约束,图论,图论,算法,c++

还可以为 :（即x3-x0<=25）

【图论】差分约束,图论,图论,算法,c++

所以我们取最短路径即可！

四.差分约束

这个即是差分约束的模型

【图论】差分约束,图论,图论,算法,c++

注意：

当出现负环的情况，我们可知，式子是无解的！（所以要用spfa算法判断负环）

当要求的两个点没有联通时，可知这两个式子没有约束！所有解都有可能！

五.例题：

3169 -- 布局 (poj.org)

【图论】差分约束,图论,图论,算法,c++

样例输入：
4 2 1
1 3 10
2 4 20
2 3 3
样例输出：

27

文章来源地址https://www.toymoban.com/news/detail-635765.html

六.参考代码

/*
4 2 1
1 3 10
2 4 20
2 3 3

27
*/

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

到了这里，关于【图论】差分约束的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！