算法的网3
2026-04-18 16:27:51
发布于：上海
这一篇是算法的网2的下一篇。它的下一篇是算法的网4
观前须知：
1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意。
2.每一句话的基础是作者浅薄的知识储备。如果你认为我讲的不对，欢迎指正。但是请友好用语。因为作者心理素质奇差无比。
——————————————————————————————————————————
这是我们的网现在的样子：
“如果是你站在我面前，张开手臂笑眯眯。那命运安排给我的酸涩与苦楚，我都甘之如饴。”
Lily Pond
这题好奇怪啊。这个数据其实不太像是最短路的数据。更像剪枝DFS。
这题看起来和DIJ和SPFA也都不是太像。难不成是BFS。
那我去做一个BFS的模板题好了。我现在有点忘了BFS怎么整了。
奇怪的电梯
这是一道BFS的模板题，我就不分析了，把代码放置一下就行。
#include<bits/stdc++.h>
using namespace std;
const int N=2e2+5;
int k[N];
int y[N];
queue<int>q;
int main(){
int n,a,b;
cin>>n>>a>>b;
for(int i=1;i<=n;i++)cin>>k[i];
q.push(a);
while(!q.empty()){
int now=q.front();
q.pop();
if(now==b){
cout<<y[b];
return 0;
}
if(b-k[b]>0&&!y[b-k[b]]){
y[b-k[b]]=y[b]+1;
q.push(b-k[b]);
}
if(b+k[b]<=n&&!y[b+k[b]]){
y[b+k[b]]=y[b]+1;
q.push(b+k[b]);
}
}
cout<<-1;
return 0;
}
我们接着看 lily pond。好吧。用BFS做会超时。
这道题的“统计路径方案”让我想到了我之前各种各样的绿色最短路似乎都是被同一个东西卡的。
是的。我不会最短路计数。
所以说，让我们来看看怎么在最短路中进行路径统计
哦。原来只要加一个计数操作就好了。试试看。
哇……写出来了喵。
感觉也没有以前想象的那么难！
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
int dis[N];
int d[N];
bool vis[N];
priority_queue<Node>pq;
vector<Node>v[N];
int mod=100003;
int main(){
int n,m;//n个顶点m条边
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back({y,1});
v[y].push_back({x,1});
}
for(int i=1;i<=n;i++)dis[i]=INT_MAX;
pq.push({1,0});
dis[1]=0;
d[1]=1;
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
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;
d[to]=d[k];
pq.push({to,dis[to]});
}else if(dis[to]==dis[k]+len){
d[to]=(d[to]+d[k])%mod;
}
}
}
for(int i=1;i<=n;i++)cout<<d[i]<<'\n';
return 0;
}
然后顺便看一个变式：路径统计
这道题目与上一道题目的区别在于：
也就是说：重边不能进行重复计算。即：这两种方案算一种：
不过这也不难办，去重边就好了。
放一下代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+1;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
int dis[N];
int d[N];
bool vis[N];
priority_queue<Node>pq;
vector<Node>v[N];
int if1[N][N][11];
int main(){
int n,m;//n个顶点m条边
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,c;
cin>>x>>y>>c;
if(if1[x][y][c]==1)continue;
if1[x][y][c]=1;
v[x].push_back({y,c});
}
for(int i=1;i<=n;i++)dis[i]=INT_MAX;
pq.push({1,0});
dis[1]=0;
d[1]=1;
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
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;
d[to]=d[k];
if(!vis[to])pq.push({to,dis[to]});
}else if(dis[to]==dis[k]+len){
d[to]=(d[to]+d[k]);
}
}
}
if(dis[n]==INT_MAX){
cout<<"No answer";
return 0;
}
cout<<dis[n]<<" "<<d[n];
return 0;
}
我这个做法很容易错，我明天来写一下要注意的点。再见。
我来了喵。
是这样的：因为我用了三维数组去记录重复的边，然后一开始设的是2005 * 2005 * 15 然后它就到了 6e7。会超空间，然后我改成了2001 * 2001 * 11 就可以了。
额。换一种做法的话，你可以直接用2005 * 2005的数组去存储边长。
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
int b[N][N];//边
int dis[N];
bool vis[N];
int d[N];//记录
int main(){
int n,e;
cin>>n>>e;
for(int i=1;i<=n;i++){
dis[i]=INT_MAX;
for(int j=1;j<=n;j++){
b[i][j]=INT_MAX;
}
}
for(int i=1;i<=e;i++){
int x,y,z;
cin>>x>>y>>z;
b[x][y]=min(b[x][y],z);
}
pq.push({1,0});
d[1]=1;
dis[1]=0;
while(!pq.empty()){
Node sum=pq.top();
int k=sum.z;
pq.pop();
if(vis[k])continue;
vis[k]=1;
for(int i=1;i<=n;i++){
if(b[k][i]==INT_MAX)continue;
int to=i;
int len=b[k][i];
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
d[to]=d[k];
if(!vis[to])pq.push({to,dis[to]});
}else if(dis[to]==dis[k]+len){
d[to]+=d[k];
}
}
}
if(dis[n]==INT_MAX){
cout<<"No answer";
return 0;
}
cout<<dis[n]<<" "<<d[n];
return 0;
}
好的。这一题暂时告一段落。我们滚回去做Lily pond。
现在这道题目看起来顺眼多了呢。直接添加方位数组，然后继续路径统计即可。
哦。还有一个比较特殊的点：这玩意儿是二维的，你在struct Node里得多加y坐标。
放一下代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int a[N][N];
typedef long long ll;
struct Node{
int zx,zy,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
int dx[8]={1,-1,1,-1,2,-2,2,-2};
int dy[8]={2,-2,-2,2,1,-1,-1,1};
vector<Node>v[N][N];
priority_queue<Node>pq;
int dis[N][N];
bool vis[N][N];
bool vis1[N][N];
ll d[N][N];
int n,m;
void dfs(int yux,int yuy,int nox,int noy){
//原来的x,原来的y,现在的x，现在的y
// cout<<yux<<" "<<yuy<<" "<<nox<<" "<<noy<<" "<<a[nox][noy]<<'\n';
if(a[nox][noy]==3||a[nox][noy]==2)return;
if(a[nox][noy]==0||a[nox][noy]==4){
Node sum={nox,noy,1};
v[yux][yuy].push_back(sum);
// cout<<"uu:"<<yux<<" "<<yuy<<'\n';
return;
}
for(int i=0;i<8;i++){
int nx=dx[i]+nox;
int ny=dy[i]+noy;
//cout<<nox<<" "<<noy<<" "<<nx<<" "<<ny<<'\n';
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&!vis[nx][ny]){
vis[nx][ny]=1;
dfs(yux,yuy,nx,ny);
}
}
}
int main(){
//int n,m;
cin>>n>>m;
int sx,sy,ex,ey;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
dis[i][j]=INT_MAX;
if(a[i][j]==3)sx=i,sy=j;
if(a[i][j]==4)ex=i,ey=j;
}
}
for(int x=1;x<=n;x++){
for(int y=1;y<=m;y++){
if(a[x][y]==2)continue;
memset(vis,0,sizeof vis);
vis[x][y]=1;
//cout<<"now:"<<x<<" "<<y<<'\n';
for(int i=0;i<8;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&!vis[nx][ny]){
// cout<<nx<<" "<<ny<<'\n';
vis[nx][ny]=1;
dfs(x,y,nx,ny);
}
}
}
}
pq.push({sx,sy,0});
dis[sx][sy]=0;
d[sx][sy]=1;
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int kx=sum.zx,ky=sum.zy;
// cout<<kx<<" "<<ky<<'\n';
if(vis1[kx][ky])continue;
vis1[kx][ky]=1;
//cout<<v[kx][ky].size()<<'\n';
for(int i=0;i<v[kx][ky].size();i++){
int tox=v[kx][ky][i].zx,toy=v[kx][ky][i].zy;
int len=v[kx][ky][i].q;
if(dis[tox][toy]>dis[kx][ky]+len){
dis[tox][toy]=dis[kx][ky]+len;
d[tox][toy]=d[kx][ky];
if(!vis1[tox][toy])pq.push({tox,toy,dis[tox][toy]});
}else if(dis[tox][toy]==dis[kx][ky]+len){
d[tox][toy]+=d[kx][ky];
}
}
}
if(dis[ex][ey]==INT_MAX){
cout<<-1;
return 0;
}
cout<<dis[ex][ey]-1<<'\n'<<d[ex][ey];
return 0;
}
唔。我觉得这道题和“断环成链”还是有出入的。
这种感觉更像是“消环”。
但是我们还可以再做一些总结：
如果有零权环出现在“最短路计数”题目上，我们可以强制介入，使所有边权>0。（应该是这样想，毕竟如果是最短路计数还有负权环不是很奇怪。既然没有负权环，那么有零权环就说明是有权值为零的边，将它们消掉即可）
今天有事。先把代码放一下。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,K,s;//n个城市，m条双向道路，k个城市被僵尸控制，不超过s条道路
ll p,qq;
struct Node{
int z;
ll q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
ll dis[N];
bool vis[N];
int t[N];//被僵尸感染的城市的编号
int w[N];//危险城市
vector<int>v[N];
queue<int>zq;
int zdis[N];//统计距离
bool zvis[N];
bool if1[N];
void bfs(){
for(int i=1;i<=n;i++)zdis[i]=INT_MAX;
for(int i=1;i<=K;i++)zdis[t[i]]=0;
while(!zq.empty()){
int k=zq.front();
zq.pop();
if(zvis[k])continue;
zvis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i];
zdis[to]=min(zdis[k]+1,zdis[to]);
if(zdis[to]<=s)w[to]=1;
if(!zvis[to])zq.push(to);
}
}
}
int main(){
cin>>n>>m>>K>>s;
cin>>p>>qq;
for(int i=1;i<=K;i++)cin>>t[i];
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=K;i++){
if1[t[i]]=1;
zq.push(t[i]);
}
bfs();
for(int i=1;i<=n;i++)dis[i]=1e18;
pq.push({1,0});
dis[1]=0;
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i];
if(if1[to])continue;
ll len=0;
if(w[to])len=qq;
else len=p;
if(to==n)len=0;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to])pq.push({to,dis[to]});
}
}
}
cout<<dis[n];
return 0;
}
“如果所有过错都原谅，那么痛苦就是咎由自取。”
是这样的：这道题目应该属于绿题里相当简单的，开头你先需要用BFS预处理出“危险城市”然后直接跑模板dij就好了。BFS的预处理也很简单。
我觉得这道题目并没有“融合”两个算法，或者说它融的不好，很割裂，本质就是两个模板的结合。
所以我不会把这道题登到算法的网那边。
下一题吧喵。
咝。这个题目的限制条件好多。
我们来列一下限制：
1.每条边有进入时间限制
2.出场时间和入场时间都必须得是k的非负整数倍。
喔。好像限制也不是很多。
唔。限制条件+最短路。这个搭配似乎是有点像网2里面提到的“通往奥格瑞玛的道路”那题。
那可能是用二分答案吧。
但是很奇怪。这个二分判定里怎么塞最短路啊。
现在好像只能摸一个疑似DFS时间复杂度的东西出来。
因为最短路并不一定是最合适啊。
怎么弄最短路啊qwq。
额。我看了题解。
他们说这是一个分层图问题。很久很久之前我曾掌握过这个技能。当然，现在并不掌握。所以说让我们重温一下这个技巧。
飞行路线
关于分层图，我在以前做过相关的学习报告，你们可以看这个，我觉得当时的我已经做的很详细了，所以我现在也不用再多说。
我也回去看了一遍我以前写的多层图学习笔记，有一点不理解的地方是：啊。为什么它不能一直往下一直往下，每一次都走边权为0的那条边，那最后答案不就是零。
错误。
因为只有k层。你如果一直往下走，最后也只有k条免费的边哦。其他的情况，我的那个帖子里也全都提了喵。
我还重新在原来的基础上花了图帮助理解：
"内心丰盈者，独行也出众。“
放一下代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
struct Node{
int z;
ll q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
priority_queue<Node>pq;
vector<Node>v[N];
ll dis[N];
bool vis[N];
int main(){
int n,m,k;//k:免费乘坐次数
cin>>n>>m>>k;
int s,t;//起点城市编号，终点城市编号
cin>>s>>t;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
for(int j=0;j<=k;j++){
//要建k+1层图。双向边
v[a+j*n].push_back({b+j*n,c});
v[b+j*n].push_back({a+j*n,c});
if(j!=k){
//最后一层就不要再往下建边啦。
v[a+j*n].push_back({b+(j+1)*n,0});
v[b+j*n].push_back({a+(j+1)*n,0});
}
}
}
pq.push({s,0});
for(int i=1;i<=n*11;i++)dis[i]=1e18;
dis[s]=0;
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
if(vis[k])continue;
vis[k]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
ll len=v[k][i].q;
if(dis[to]>dis[k]+len){
dis[to]=dis[k]+len;
if(!vis[to])pq.push({to,dis[to]});
}
}
}
ll ans=1e18;
for(int i=0;i<=k;i++){
ans=min(ans,dis[t+i*n]);
}
cout<<ans;
return 0;
}
好的，我们回归原来的题目吧。
我去。不太对。分层图和多层图似乎不是一个东西。SOSOSOSOSOS。
好吧。看了一个题解说思路要一层一层地理清楚。可能这就是CSP真题的魅力吧。
那从哪里开始呢？肯定是从特殊性质开始。（或者n<=10可以暴力）
当a[i]=0，意味着没有时间限制，所以我们可以从零时刻到达起点。
那我们的限制就是要经过k的非负整数倍的边。
（from洛谷OMG_wc)
这个就是35pts的代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int K=1e2+5;
struct Node{
int z,q;
};
queue<Node>q1;
vector<int>v[N];
int dis[N][K];//d[i][j]表示：到达i这个点满足时间modk=j的最短时间
int main(){
int n,m,kk;//k:发车间隔
cin>>n>>m>>kk;
for(int i=1;i<=m;i++){
int uu,vv,aa;
cin>>uu>>vv>>aa;
//单向边
v[uu].push_back(vv);
}
memset(dis,-1,sizeof dis);
q1.push({1,0});
dis[1][0]=0;
while(!q1.empty()){
Node sum=q1.front();
q1.pop();
int k=sum.z;
for(int i=0;i<v[k].size();i++){
int to=v[k][i];
int len=sum.q+1;
if(dis[to][len%kk]==-1){
dis[to][len%kk]=len;
q1.push({to,len});
}
}
}
cout<<dis[n][0];
return 0;
}
我觉得这个子任务似乎已经有了一点黄的难度了。
那我们先对子任务进行分析吧。
是这样的：当最短路有时间限制的时候的时候（特质需要时间是x的倍数），我们可以在dis数组后面加一维，dis[i][j]表示到达第i个点的时间%x=j。
然后我们接着看怎么完成100pts.
100pts就是在原来的基础上加上到达每个顶点的时间限制。如何解决时间限制呢。
不难想到，如果到达了一个点x,时间限制是a。当前时间是y。如果y<a，那我们应该在y上增加一个k的非负整数倍数，使得加上之后的数值>a。
那我们具体应该加多少呢。
比如说，时间限制是5当前时间点是0，需要是3的倍数。
那么应该是。关于为什么：求出a-y，然后求出它们之间差了错少个k。不能向下取整。
由于这样边权就不是1了。那么自然，不能使用BFS。我们得用最短路DIJ。
唔。这差不多就是大致思路了。
我们来放一下代码吧：
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
const int K=1e2+5;
struct Node{
int z,mo,d;
friend bool operator < (Node a,Node b){
return a.d>b.d;
}
};
priority_queue<Node>pq;
vector<Node>v[N];
int dis[N][K];
bool vis[N][K];
int main(){
int n,m,kk;
cin>>n>>m>>kk;
for(int i=1;i<=m;i++){
int uu,vv,aa;
cin>>uu>>vv>>aa;
v[uu].push_back({vv,uu,aa});
}
for(int i=1;i<=n;i++){
for(int j=0;j<=kk;j++){
dis[i][j]=INT_MAX;
}
}
pq.push({1,0,0});
dis[1][0]=0;
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
int mod=sum.mo;
int di=sum.d;
if(vis[k][mod])continue;
vis[k][mod]=1;
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
int len=1+di;
if(v[k][i].d>di)len+=(v[k][i].d-di+kk-1)/kk*kk;
if(dis[to][len%kk]>len){
dis[to][len%kk]=len;
pq.push({to,len%kk,len});
}
}
}
if(dis[n][0]==INT_MAX)cout<<-1;
else cout<<dis[n][0];
return 0;
}
这是这道题目的第一个做法。我看到题解里面说，这道题还有二分+分层图的做法。等我分析完第一个做法，我们就去看看第二个做法好了。
分析：
唔。怎么说呢。在做这道题的时候我觉得这题还挺难的。做起来也挺吃力。
但是现在做完之后再看，我反而觉得也不是很难。
最短路想要玩出花，无非就是加限制条件。
不同的限制条件有不同的应对方法。
等到我做完所有最短路绿，我会把它们重新都在做一遍，让后弄一个做法上的整理。
这道题目的限制条件有两个：
1.必须经过k的倍数条边
2.进入边的时间有限制
对于第一个限制条件，我们的做法是：改变dis数组的定义。
我觉得这个做法很妙。
第二个限制条件更加简单，你只需要在原地等待一些时间就好了。（具体等待多少，我在上面有分析）
现在我要去学一下第二种做法。拜拜。
吓哭了
有帮助，赞一个