差分约束算法

差分约束是为了解决这样一组不等式问题：

这个咋解决》我们来看
对于某个下标k而言，提取出关于其的所有不等式，（其中xk在第一个),也就是

xk-x1<=m1
xk-x2<=m2
xk-x3<=m3....
1
2
3

对于这些不等式相当于是
xk取min(x1+m1,x2+m2,x3+m3,…)
那么这个时候如果可以想到图论算法的话就是，从x1,x2,x3…这些点连出一条指向xk的边，权值为m1,m2,m3,…（我之前写错是因为边连反了，权值也是反的,)用最短路算法来解决这个问题，那么就变成：求一个源点到各个点的最短路问题，这个时候，注意无解的情况，如果存在一个负权环负权环的定义应为环上的权值之和为负值，那么就说明出现了循环关系，也就是，我们来看：

x1-x2<=-1
x2-x3<=-2
x3-x1<=-2
1
2
3

这个是个怪圈也就是无解的情况。
那如果有正权环呢？
我们来看

x1-x2<=1
x2-x3<=2
x3-x1<=2
1
2
3

如果x1取1，那么x2可以取0，x3可以取-2
他们的大小关系是不一定的
但是上面那个怪圈是出现了循环小于的情况，所以无解
正权环可以理解成x1可能比x2大一点，但也有可能小于x2，负权的时候是一定小于
如果你觉得本蒟蒻写的不咋地，请移步：
神犇的讲解
题：
差分约束算法
注意由于有负权环，又需要检查负权环，所以使用Bellman-Ford算法即可
代码：

#include
using namespace std;
#define INT_MAX 0x3f3f3f3f
const int length = 5e3 + 5;
vector<pair<pair<int, int>, int>> edge;
int dp[length];
int main(void)
{
	int n, m;
	scanf_s("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		scanf_s("%d%d%d", &a, &b, &c);
		edge.push_back({ {b,a},c });
	}
	//使用b_f算法
	for (int i = 1; i <= n; i++)
	{
		dp[i] = INT_MAX;
	}
	for (int i = 0; i < n - 1; i++)
	{
		for (int i = 0; i < m; i++)
		{
			int a = edge[i].first.first;
			int b = edge[i].first.second;
			int c = edge[i].second;
			dp[b] = min(dp[a] + c, dp[b]);
		}
	}
	int flag = 1;
	for (int i = 0; i < m; i++)
	{
		int a = edge[i].first.first;
		int b = edge[i].first.second;
		int c = edge[i].second;
		if (dp[b] > dp[a] + c)
		{
			flag = 0;
			break;
		}
	}
	if (flag == 0)
	{
		printf("NO");
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			printf("%d ", dp[i]);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55