img

差分约束

这个只在做题的时候提到过，因此想着把这个总结一下，方便以后观看。

概念

差分约束系统是一种特殊的N元一次不等式组，它包含N个变量\(X_1~X_n\),以及M个约束条件，每个约束条件都是由两个变量作差构成的，形如

\(X_i−X_j<=C_k(C_k是常数)注：必须是形如上式这样的形式如果不是，需要转化成上式\)

$需要解决的问题是：求一组解X_1 = a_1 , X_2 = a_2 . . . $

\(使 所 有 约 束 条 件 都 能 满 足 X_1 = a_1,X_2 = a_2...使所有约束条件都能满足\)

\(X_i−X_j<=C_k\)

可以变形为：

\(X_i<=X_j+C_k\)

而它与最短路问题中的三角形不等式\(dist[y]<=dist[x]+z\)相似 所以可以把所有形如

\(X_i<=X_j+C_k\) \(的式子看成是从 j 出发向 i 连一条长度为C_k的有向边\)

求解该不等式组的解就是对这个不等式所建的图求最短路径。

条件限制或者说是补充

对于求单源最短路问题， 源点需要满足条件：从源点出发，一定可以走到所有的边。需要找一个可以走到所有边的源点。

解题步骤

先将每个不等式 \(x_i < = x_j + c\)

转化为一条从 j 走到 i ，长度为c的一条边 找一个超级源点（或者建立一个虚拟源点），使得该源点一定可以遍历到所有边 从源点求一遍单源最短路 结果1：如果存在负环，则原不等式组一定无解 结果2：如果没有负环，则dist[i]就是原不等式组的一个可行解。

【模板】差分约束

题目描述

给出一组包含 \(m\) 个不等式，有 \(n\) 个未知数的形如：

\[ \begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}\]

的不等式组，求任意一组满足这个不等式组的解。

输入格式

第一行为两个正整数 \(n,m\)，代表未知数的数量和不等式的数量。

接下来 \(m\) 行，每行包含三个整数 \(c,c',y\)，代表一个不等式 \(x_c-x_{c'}\leq y\)。

输出格式

一行，\(n\) 个数，表示 \(x_1 , x_2 \cdots x_n\) 的一组可行解，如果有多组解，请输出任意一组，无解请输出 NO。

样例 #1

样例输入 #1

1
2
3
4
3 3
1 2 3
2 3 -2
1 3 1

样例输出 #1

1
5 3 5

提示

样例解释

\(\begin{cases}x_1-x_2\leq 3 \\ x_2 - x_3 \leq -2 \\ x_1 - x_3 \leq 1 \end{cases}\)

一种可行的方法是 \(x_1 = 5, x_2 = 3, x_3 = 5\)。

\(\begin{cases}5-3 = 2\leq 3 \\ 3 - 5 = -2 \leq -2 \\ 5 - 5 = 0\leq 1 \end{cases}\)

数据范围

对于 \(100\%\) 的数据，\(1\leq n,m \leq 5\times 10^3\)，\(-10^4\leq y\leq 10^4\)，\(1\leq c,c'\leq n\)，\(c \neq c'\)。

评分策略

你的答案符合该不等式组即可得分，请确保你的答案中的数据在 int 范围内。

如果并没有答案，而你的程序给出了答案，SPJ 会给出 There is no answer, but you gave it，结果为 WA；
如果并没有答案，而你的程序输出了 NO，SPJ 会给出 No answer，结果为 AC；
如果存在答案，而你的答案错误，SPJ 会给出 Wrong answer，结果为 WA；
如果存在答案，且你的答案正确，SPJ 会给出 The answer is correct，结果为 AC。

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt;
const int N=5005;
int dis[N];
bool vis[N];
int num[N];
struct edge
{
	int to, w,next;
}e[2*N];
int head[N];
queue<int>q;
void add(int u,int v,int w)
{
	e[++cnt].to=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
//链式前向星
bool spfa(int x)
{
	dis[x]=0;
	q.push(x);
	vis[x]=1;
	num[x]++;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=0;i=e[i].next)
		{
			if(dis[e[i].to]>dis[u]+e[i].w)
			{
				dis[e[i].to]=dis[u]+e[i].w;
				if(!vis[e[i].to])
				{
					q.push(e[i].to);
					vis[e[i].to]=1;
					num[e[i].to]++;
					if(num[e[i].to]==n+1)
					{
						return 0;
                        //有负环
					}
									
				}
			}
		}
		
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		dis[i]=1e9;
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(v,u,w);
	}
	for(int i=1;i<=n;i++)
	{
		add(n+1,i,0);
	}
    //超级源点的建立
		if(!spfa(n+1))
		{
			cout<<"NO"<<'\n';
			return 0;
		}
	for(int i=1;i<=n;i++)
	{
		cout<<dis[i]<<" ";
	}
	
	
}