【模板】差分约束算法

题目描述

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

$$\{\begin{array}{l}{x}_{c_1}-x_{c_1^{\prime }}\le y_1\\ x_{c_2}-x_{c_2^{\prime }}\le y_2\\ \cdots \\ x_{c_m}-x_{c_m^{\prime }}\le y_m\end{array}$$

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

输入格式

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

接下来 $m$ 行，每行包含三个整数 $c,c^{\prime },y$，代表一个不等式 $x_c-x_{c^{\prime }}\le y$。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

5 3 5

提示

样例解释

$\{\begin{array}{l}{x}_1-x_2\le 3\\ x_2-x_3\le -2\\ x_1-x_3\le 1\end{array}$

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

$\{\begin{array}{l}5-3=2\le 3\\ 3-5=-2\le -2\\ 5-5=0\le 1\end{array}$

数据范围

对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^3$，$-10^4\le y\le 10^4$，$1\le c,c^{\prime }\le n$，$c\ne c^{\prime }$。

评分策略

你的答案符合该不等式组即可得分，请确保你的答案中的数据在 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。

差分约束模板

我们知道在SPFA中，在单源最短路问题中，如果存在一条 𝑖 → 𝑗 长为 𝑤 的边，在计算1
号点到每个点的最短路后，一定有 𝑑𝑖𝑠[𝑖] + 𝑤 ≥ 𝑑𝑖𝑠[𝑗]。
$x_i+c\ge x_j$ 与其相同
所以若存在$x_i+c\ge x_j$,使用图论便是：连边(i,j,c)

代码

#include<bits/stdc++.h>
using namespace std;
const int M=1e4;
int dis[M],cnt[M];
bool inQueue[M];
queue<int> Q;
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
#define for_(i,a,b) for(int i=(a);i>=(b);i--)
#define _rep(i,a,b) for(int i=(a);i<(b);i++)
vector<pair<int, int> > edges[M];
void add(int u,int v,int w){edges[u].emplace_back(v, w);
}
bool spfa(int s,int n){memset(dis, 0x3f, sizeof(dis));dis[s] = 0;Q.push(s);inQueue[s] = true;while (!Q.empty()) {int x = Q.front();Q.pop();inQueue[x] = false;for (auto edge: edges[x]) {if (dis[edge.first] <= dis[x] + edge.second)continue;dis[edge.first] = dis[x] + edge.second;if (!inQueue[edge.first]) {Q.push(edge.first);inQueue[edge.first] = true;cnt[edge.first]++;if (cnt[edge.first]>1+n) return false;}}}return true;
}
int main(){int n,m;cin>>n>>m;_for(i,1,n) add(0,i,0);_for(i,1,m){int u,v,w;cin>>v>>u>>w;add(u,v,w);}if (!spfa(0,n)) {cout<<"NO";return 0;}_for(i,1,n) cout<<dis[i]<<' ';return 0;
}

分析

spfa模板+上面的分析，这里说下存图：

vector<pair<int, int> > edges[M];

就是 vector<pair<v,w> >edges[u];