此篇主要是记录关于spfa与同余最短路的贴,那么先按照难度顺序,或者说技能树顺序来吧。
文末附上了我看过的所有帖子,基本来源于洛谷,如果其他人看到了这个学习记录,看我的感觉讲的不够清楚,没理解,请自行移步到这些原帖,一定是很容易懂的
P5960 【模板】差分约束
题意:
也就是给出n个数,然后这n个数有m个不等式,问满足要求的一组解。
思路:
本人太笨,一开始还觉得只要借助不等式算区间得值之类的就能做出来
1.想联想到最短路,转换成图论问题你必须要观察到 ,这个公式与最短路非常相似,不然是转换不到图论去的。能转换成图的关系就是,两个点之间的差值不能超过y1,如此一来,最短路就刚好适用,因为最短路可以提供两个点的间接关系,这是这道题的关键。
2.接下来要加入超级源点,因为不等式提供的是相对关系,你总得要一个具体的值对吧。但是不能是任意挑一个点,因为构建出来的图并不一定是连通图,设置所有的点与超级源点的路径为0
即,因为都是相对关系,所以不影响结果的得出,这样就联通了整个图,一次就可以了,
不过我觉得改成联通图独立判断应该也能行但是没啥必要。
3.接下来就是spfa的板子,推荐看D03 最短路 Bellman-Ford 算法 SPFA 算法——信息学奥赛算法_哔哩哔哩_bilibili
添边是不能双向边的,这并不是无向边,的关系只能得到单向边,如果你构建无向边(双向边),其实是创造了一个新关系。
这个图出现负环的情况是什么,负环其实就是,自己小于等于自己是错误的,很明显是NO答案。负环是指自身环无限更新至-∞的情况,并非有负边就是负环,其实负环就是互相要求对方在关系传递后一个比一个小,又要比对方大又要比对方小是冲突的。如果能保持稳定存在的关系,就不是NO
代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 2023;int n,m;
vector<pair<int,int> > mp[N];
int vis[N];
int dis[N];
int cnt[N];bool spfa(int x){queue<int> q;vis[x]=1;dis[x]=0;q.push(x);while(q.size()){auto t=q.front();q.pop();vis[t]=0;for(auto [u,v] : mp[t]){if(dis[u]>dis[t]+v){dis[u]=dis[t]+v;if(vis[u]) continue;vis[u]=1;cnt[u]++;if(cnt[u]==n+1) return false;q.push(u);}}}return true;
}void solve(){cin >> n >> m;for(int i=0;i<m;i++){int x,y,c;cin >> x >> y >> c;mp[y].push_back({x,c});}for(int i=1;i<=n;i++){dis[i]=INF;mp[0].push_back({i,0});}if(!spfa(0)){cout << "NO" << endl;}else{for(int i=1;i<=n;i++){cout << dis[i] << " ";}}}signed main(){IOS;int t=1;
// cin >> t;while(t--){solve();}
}
那么spfa用于判负环的最短路初步学习就到这了。
总结:数学关系能转换成最短路联系,因为最短路能保持着原有的传递关系,且spfa能解决负环问题。
P3403 跳楼机
题意:
思路:
1.这题先可以转换成给出3个数字操作,能得到哪些数字,但没有要求最小操作数。所以可以看成,任何一个新得到的数加上别的数能得到的数,现在我们假设得到了一个数字,它可以+a*k,也就是构成了一个类似于周期循环一样的,是不是代表一个数的相同余数的最小值被得到后,之后处于相同余数(每个周期的相同余数)的所有值都可以被得到?
这个思路可能并不好不适用所有人,该想法来自蓝桥杯的一道题,我当时并不会同余最短路……但是思路想到了同余最短路……P8646 [蓝桥杯 2017 省 AB] 包子凑数 题解 - 洛谷专栏如果感兴趣可以看这个。
2.现在明确如果知道一个同一个余数的最小值知道后,那么在这个相同余数下的所有以a构成循环的数之后一定能通过+a得到。那么问题转换成了,怎么求出每个%a的余数,最小的数是谁。
那么很明显最短路利用剩下的b,c得到就行了,(x+a)%a==x,a的使用是无意义的。
3.如果还用1的话,明显加大了代码实现的复杂度,不妨h--,然后转换成0到h-1的高度进行余数的计算就可以了。后面数字的计算其实就是(h-dis[x])/a+1,这个自己画个图或者想想应该能想明白吧?类似于还有多少个周期这样的意思。然后这道题可以不用spfa得到,因为没有负权,如此一来也不存在负环,可以用dij,其实都是一样的。
spfa代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 2023;int dis[N];
int vis[N];
int cnt[N];
vector<pair<int,int> > mp[N];bool spfa(int x,int a){queue<int> q;vis[x]=1;dis[x]=0;q.push(0);while(q.size()){auto t=q.front();q.pop();vis[t]=0;for(auto [u,v] : mp[t]){if(dis[u]>dis[t]+v){dis[u]=dis[t]+v;if(vis[u]) continue;vis[u]=1;cnt[u]++;q.push(u);}}}return true;
}void solve(){int h;cin >> h;h--;int a,b,c;cin >> a >> b >> c;for(int i=0;i<=a;i++){dis[i]=INF;mp[i].push_back({(i+b)%a,b});mp[i].push_back({(i+c)%a,c}); }spfa(0,a);int ans=0;for(int i=0;i<a;i++){if(dis[i]<=h){ans+=(h-dis[i])/a+1;}}cout << ans << endl;}signed main(){IOS;int t=1;
// cin >> t;while(t--){solve();}
}
dij代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define int128 __int128
#define endl '\n'
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 2e5+10;
const int INF = 1e18;
const int MOD = 2023;int dis[N];
int vis[N];void dij(int n,int b,int c){priority_queue<pair<int,int> ,vector<pair<int,int>> , greater<pair<int,int>> > q;dis[0]=0;q.push({0,0}); //点 最短路while(q.size()){auto [v,u]=q.top();q.pop();if(vis[u]) continue;vis[u]=1;int nex=(u+b)%n;if(dis[nex]>dis[u]+b){dis[nex]=dis[u]+b;q.push({dis[nex],nex});}nex=(u+c)%n;if(dis[nex]>dis[u]+c){dis[nex]=dis[u]+c;q.push({dis[nex],nex});}}
}void solve(){int h;cin >> h;h--;int a,b,c;cin >> a >> b >> c;for(int i=0;i<=a;i++){dis[i]=INF;}dij(a,b,c);int ans=0;for(int i=0;i<a;i++){if(dis[i]<=h){ans+=(h-dis[i])/a+1;}}cout << ans << endl;}signed main(){IOS;int t=1;
// cin >> t;while(t--){solve();}
}