2023.5.6 写的太烂了重新写
差分约束系统
定义
差分约束系统是一种特殊的 \(n\) 元一次不等式组,它包含 \(n\) 个变量 \(x_{1},x_{2},...,x_{n}\) 以及 \(m\) 个约束条件,每一个约束条件都是两个其中的变量做差构成的,形如 \(x_{i}-x_{j}\le c_{k}\),其中 \(1\le i,j\le n,i\ne j,1\le k\le m\) 并且 \(c_{k}\) 是常数(可以为正数或非正数)。
------- OI Wiki
通俗一点讲,这类问题都是给定 \(n\) 个变量,\(m\) 个限制,类似于:
有了这些条件,一般的题目会让你求出一组合法的解,也就是求这 \(n\) 个变量的合法的值。
过程
我们可以建一个超级源点,然后向每一个点连一条边权为 \(0\) 的边,然后跑单源最短路;而上面的 \(m\) 个限制都可以变形为 \(x_{i}\le x_{j}+c_{k}\),这个东西很容易想到我们在跑最短路的时候的松弛操作里的 \(dis[v]\le dis[u]+w\),因此我们就可以把每一个变量看作是一个图中的点,对于每一个条件 \(x_{i}-x_{j}\le c_{k}\),从 \(j\) 向 \(i\) 连一条边权为 \(c_{k}\) 的有向边。
我们在求解的时候一般用 SPFA 来跑,虽然他最坏的时间复杂度是 \(O(nm)\) 的,但是我们的差分约束里面要是有负环的话,就说明是无解,再加上有负边权,SPFA 这个已死的算法成了最好的方法,更何况他在一些随机的图中跑的飞快。
最后一个问题,最后转化的式子是 \(x_{i}\le x_{j}+c_{k}\),为什么跑最短路?
但是我觉得,当你建图的时候使用的是 \(x_{i}-x_{j}\le c_{k}\) 形式的方程组建图时,即 \(j\) 向 \(i\) 连一条权值为 \(c_{k}\) 的边,应该选择跑最短路。
如果使用的是 \(x_{i}-s_{j}\ge c_{k}\) 形式的方程组来建图时,应该选择跑最长路。文章来源:https://www.toymoban.com/news/detail-435235.html
P5960 【模板】差分约束算法
code:文章来源地址https://www.toymoban.com/news/detail-435235.html
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 50100
using namespace std;
int n,m,cnt,head[N];
queue<int>q;
struct SB{int w,v,next;}e[N<<1];
int dis[N],tot[N],vis[N];
inline void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
int SPFA()
{
q.push(0);
vis[0]=1;
tot[0]++;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
q.push(v);
vis[v]=1;
tot[v]++;
if(tot[v]==n+1)
return 0;
}
}
}
return 1;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
dis[i]=INF;
for(int i=1;i<=n;i++)
add(0,i,0);
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
add(y,x,z);
}
if(!SPFA())
cout<<"NO"<<endl;
else
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}
到了这里,关于差分约束学习笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!