Description
一个差分约束系统是这样的。
给定一组包含 \(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} \]求任意一组可行解。
Solution
观察这个式子：
\(x_{c1}-x_{c'1} \le y_1\)
我们将这个式子移项，得：
\(x_{c1}\le y_1+x_{c'1}\)
观察到这个式子类似于求最短路中的松弛操作。我们可以将 \(x_{c'1}\) 到 \(x_{c1}\) 连一条长度为 \(y_1\) 的边。然后跑最短路即可。
至于从哪个点开始跑呢？实际上我们从任意一个点开始跑都可以。但是很多情况我们得到的图都是不连通的。因此我们习惯上人为添加一个超级源点。
也就是从 \(0\) 号节点向每一个点连一条长度为 \(0\) 的边。也就是人为添加了以下约束条件：
\[\begin{cases} x_{c_1}-x_{0}\leq 0 \\x_{c_2}-x_{0} \leq 0 \\ \cdots\\ x_{c_m} - x_{0}\leq 0\end{cases} \]注意到此时所有点的最短路都 \(\le 0\)。如果我们想要非负解呢？
这也很简单，根据不等式的基本性质，将所有满足约束的 \(x_i\) 同加上一个值，仍然满足约束。我们只需要在超级源点连边的时候赋为 \(w\) 即可。
这样我们得到的就是 \(\forall x_i \le w\) 的一组解。事实上，可以证明这是满足 \(\forall x_i \le w\) 的最大解。
那么如何求最小解呢？只需要求最长路即可。
对于判定无解，我们只需要在求最短路的时候判负环即可。如果出现负环，则最短路无解，显然不等式组无解。
题目中有时给出的不等式组并非差分约束系统一般形式，我们可以通过一系列转换。灵活应用转换为朴素查分约束系统。
模板代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PAIR;
const int N = 100010;
const int INF = 0x3f3f3f3f;
int vis[N];
int dist[N];
int cnt[N];
vector <PAIR> Edge[N];
int n,m;
bool spfa()
{
queue <int> q;
q.push(0);
vis[0] = 1;
dist[0] = 0;
while(!q.empty())
{
int u = q.front();
// cout<<cnt[u]<<endl;
if(cnt[u] >= n)
{
return false;
}
q.pop();
vis[u] = 0;
for(auto v:Edge[u])
{
int vv = v.first,ww = v.second;
if(dist[vv] > dist[u] + ww)
{
cnt[vv] ++;
//cout<<cnt[u]<<endl;
dist[vv] = dist[u] + ww;
if(!vis[vv]) q.push(vv);
}
}
}
return true;
}
int main()
{
// freopen("input.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int v,u,w;
cin>>v>>u>>w;
Edge[u].push_back({v,w});
}
for(int i=1;i<=n;i++) Edge[0].push_back({i,0});
for(int i=1;i<=n;i++) dist[i] = INF;
if(!spfa())
{
cout<<"NO"<<endl;
return 0;
}
for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
cout<<endl;
return 0;
}