洛谷 P5960 【【模板】差分约束算法】/差分约束算法入门

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了洛谷 P5960 【【模板】差分约束算法】/差分约束算法入门，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2252字，纯文字阅读大概需要4分钟。

内容图文

啊这，为什么一道看上去完全跟图论无关的题有图论标签。

---

正题：

差分约束系统&&转化： 顾名思义，差分约束系统就是给你很多个形如\(x_1-x_2\leqslant c_k\)的不等式（其中c为常数），让你求出一组解或者判断无解。看上面的式子，把它变成这样：\(x_1\leqslant x_2+c_k\)，是不是很熟悉，长得就跟最短路里面的三角形不等式一模一样，这样一来，我们就可以把\(x_2\)向\(x_1\)（注意，是2连向1，因为最短路中是\(\geqq\)，这里是$\leqslant $，所以要反着来）连一条边(有向的),然后跑最短路。

为什么是正确的呢? 在多个不等式中，对于一个数\(x\)，我们可以通过自己所在的不等式来确定自身范围，而一个不等式有两个未知数，另外一个未知数又通过其他不等式与其他未知数相关系起来，这就搭建起来了一条条边，组合成图，从任意一个点出发，一个一个点的满足，最终肯定会到达x的，这样也就得出了一组解。

差分约束系统也可以跑最长路 差分约束系统中，最短路和最长路的区别就是：最短路是求的所有解中最大的一组，而最长路相反。看这样一组式子： \(\begin{cases}x_2-x_1\leqslant c_1\\x_3-x_2\leqslant c_2\\x_3-x_1\leqslant c_3\end{cases}\) 我们可以得出这样两个式子：\(\begin{cases}x_3\leqslant x_1+c_3\\x_3\leqslant x_1+c_1+c_2\end{cases}\) ，可以得出，约束\(x_3\)的有两个条件，正好图里面也有两条路。我们要求\(x_3\)的最大值时，取的肯定是\(x_1+c_3\)和\(x_1+c_1+c_2\)里面的最小值，这样才能满足所有的约束条件，也就是最短路了。最长路求的最小解同理。

什么情况无解（以下均以最短路为例）： 最短路里面有负环时无解。再看一组式子：\(\begin{cases}x_1-x_3\leqslant 3\\x_2-x_1\leqslant -5\\x_3-x_2\leqslant -3\end{cases}\)，这种情况下，转化成图后就会出现负环，而这组式子最后可以得出一个式子：\(x_3\leqslant x_3-5\)，跑最短路时，为了满足这个条件，就会一直更新一直更新，也就是出现了负环。所以，有负环的时候，不等式组无解。

接下来就是代码时间咯（当时\(SPFA\)一直\(RE\)，也不知道为什么，后来索性写了\(Ford\)，还是\(Ford\)香啊~）:

#include <bits/stdc++.h>
using namespace std;
struct node{
	int l , r , w;
};
node e[5010];
int n , m;
int dis[5010];
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> e[i].r >> e[i].l >> e[i].w;	//注意l和r反过来了 
	for(int i = 1; i <= n - 1; i++)
		for(int j = 1; j <= m; j++)
			dis[e[j].r] = min(dis[e[j].r] , dis[e[j].l] + e[j].w);	//松弛 
	for(int j = 1; j <= m; j++)
		if(dis[e[j].r] > dis[e[j].l] + e[j].w){	//判断是否有负环 
			cout << "NO";
			return 0;
		}
	for(int i = 1; i <= n; i++) cout << dis[i] << " ";
	return 0;
}

内容总结

以上是互联网集市为您收集整理的洛谷 P5960 【【模板】差分约束算法】/差分约束算法入门全部内容，希望文章能够帮你解决洛谷 P5960 【【模板】差分约束算法】/差分约束算法入门所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---