最短路:差分约束
2025-06-15 19:01:23
发布于：上海
3阅读
0回复
0点赞
emmm...是的,又是最短路.
前置知识点:
1.邻接表2.SPFA
例题:P5960 【模板】差分约束
差分约束系统:一个由n个变量和m个约束条件(不等式)组成.
其实就是求解一组变量的不等式组的算法.
题意很清楚,这里就不进行分析了.
思路:
(这题的写法还是蛮多的,此处介绍一种)
此题一眼看不出来是最短路.这是难点.
就算知道是最短路后,也不知道也么写.这更是难点.
这里,作者将分析如何使用最短路解决此题.
方案:将不等式转换.
以样例为例:
3 3
1 2 3
2 3 -2
1 3 1
这个
可以转换为这个
似乎令人眼熟 ,不是吗?
(松弛)
所以,我们可以将是做,而这里的len就是点和点之间的一条路径(单向)
那么整个样例就可以转换成:
而且,同样地,就可以转换成.
但是也会诞生一个问题,在最短路中,表示的是起点到点的距离.
那么此时的起点是谁? 答:是超级原点.
它长这样:
此时的"0"就是那个超级原点.
超级原点和图中的每一个点都有一条长度为0的边.
因为没有明确的"起点",所以才会有超级原点.
添加一个超级原点,其实就是将某一个点(0/n+1)与其他所有的点增加一条长度为0的边.
代码如下:
for(int i=1;i<=n;i++){
v[0].push_back({i,0});
}
但是,可能会有人问:
如果说所有都是0的话,输出的不是也全都是0吗?
这是因为,不等式中,会有负数的存在.
所以说,在这种方法下求解出的不等式组,它的每一个变量,都是的.
最后还有一个问题:无解.
其实,这里的无解也很好理解,就是所谓的:负环.
在做SPFA的时候,判断一下负环就可以判断不等式是否无解了.
代码:
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v[10005];
int dis[10005];
bool vis[10005];
int su[10005];
priority_queue<Node>q;
bool spfa(){
for(int i=0;i<=n+1;i++){
dis[i]=1e9;
}
dis[0]=0;
q.push({0,0});
vis[0]=1;
while(!q.empty()){
Node sum=q.top();
q.pop();
int k=sum.z;
vis[k]=0;
su[k]++;
if(su[k]>n){
return 0;
}
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to]){
vis[to]=1;
q.push({to,dis[to]});
}
}
}
}
return 1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
v[0].push_back({i,0});
}
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
v[y].push_back({x,z});
}
if(spfa()){
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
}else {
cout<<"NO";
}
return 0;
}
应用范围:
差分约束主要用于一些有"至少","至多"字眼的题目
这里空空如也
有帮助，赞一个