标签：use qu int 差分 约束 leq ddis dis

差分约束

对于形如：

\[\begin{cases} x_{c_{1}}-x_{c_{1}'}\leq y_1 \\ x_{c_{2}}-x_{c_{2}'}\leq y_2 \\ ...\\ x_{c_{n}}-x_{c_{n}'}\leq y_n \\ \end{cases} \]

对于单个式子而言\(x_{c_{1}}-x_{c_{1}'}\leq y_1\)，可转换为\(x_{c_{1}}\leq x_{c_{1}'}+y_1\)，而在图论中的点与点的距离也可以表示成这种样子，也就是点\(c_1'\)到\(c_1\)有一条权值为\(y_1\)的单向边

建图，用SPFA判断是否有负环即可判断是否有解，并且最后的dis就是一个可行解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fo(i,n) for(int i = 1;i <= n;i++)
#define debug(i,x) cout << "case" << (i) << ":" << x << endl;
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
const int inf = 1e9;
const int MAXN = 5e3 + 10;
ll num[MAXN],dis[MAXN];
bool use[MAXN];
vector<pair<int,int>> ed[MAXN];
int n,m;
void init(){
	memset(dis,1e9,sizeof(dis));
}
bool spfa(){
	dis[1] = 0;
	queue<int> qu;
	fo(i,n){
		qu.push(i);
		use[i] = 1;
		num[i]++;
	}
	while(!qu.empty()){
		int u = qu.front();
		use[u] = 0;
		qu.pop();
		for(auto pa:ed[u]){
			int v = pa.first,ddis = pa.second;
			if(ddis + dis[u] < dis[v]){
				dis[v] = ddis + dis[u];
				if(!use[v]){
					num[v]++;
					use[v] = 1;
					qu.push(v);
					if(num[u] >= n)//出现负环
						return 0;
				}
			}
		}
	}
	return 1;
}
int main()
{
	cin >> n >> m;
	init();
	for(int i = 1;i <= m;i++){
		int u,v,dis;cin >> u >> v >> dis;
		ed[v].push_back({u,dis});
	}
	bool f = 1;
	if(!spfa()){
		f = 0;
	}
	if(f)
		fo(i,n)
			cout << dis[i] << ' ';
	else
		cout << "NO" << endl;
}

标签：use,qu,int,差分,约束,leq,ddis,dis
From： https://www.cnblogs.com/xxcdsg/p/17544280.html