算法的网4
2026-05-15 16:18:47
发布于：上海
这一篇是算法的网3的下一篇。
观前须知：
1.由于 作者的精神状态十分低下。所以可能会出现讲题讲到一半开始胡言乱语的情况。不用太过在意。
2.每一句话的基础是作者浅薄的知识储备。如果你认为我讲的不对，欢迎指正。但是请友好用语。因为作者心理素质奇差无比。
——————————————————————————————————————————
这是我们的网现在的样子：
我们接着上一篇提到的，来讲一讲旅游巴士的第二种做法。
喔喔喔喔喔喔喔。我有点恍然大悟了。
分层图本身可能比不是一定要把每个点都以在图上添加k个来实现的。（比如说P4568飞行路线）
它也可以是：一个点有k个状态。
而dis[i][j]就是表示第i个点的j个状态。
这是我上一篇写的：
它的第二维就是状态。虽然是n个点，但实际上是k*n个点的分层图。
哦。所以没有第二种做法。
原来如此。
好的，那我们看下一题吧。
陌路寻诗礼
唔。我好像没见过这种要求。好神奇啊。
这道题目的要求是：给出n（节点数）,m（边数）,k（边权取值范围）和m条边。
问：如何安排m条边的边权，使得从点1到其他城市的最短路径为1.
我的初步思路是跑BFS，然后在跑的过程中给边加边权。
那么如何赋值边权呢。
我不会。
啊啊啊啊。怎么构造啊。
想太久了没想出来又去看题解了。我觉得我好**。但关键是不看也做不出来。
怎么办啊。
那我多做一点最短路绿好了。我觉得只练十题太少了。练二十题好了。
牛的旅行
社交网络
道路选择
最长距离
黑暗城堡
(上面的这些是前面的十多题遗留的，下面的十题是新选择的）
团
图上交互题
car的旅行路线
最优贸易
灾后重建
房间最短路问题
跑路
Cleaning Shifts S
电话
采蘑菇
好的，题挑完了，我们接着看陌路寻诗礼。
好的，我看完题解了。
其实这个题解让我感觉很诡异：就是我觉得，这个思路似乎是不难想的，或者说理所应当的。但是同时我认为，这个做法像是从天上掉下来的一样。（也就是我当时在想题的时候，从来没有想过这个方面）
它居然是可以直接加的嘛……好震惊。
我再看完之后的感觉是很奇怪，因为在我的大脑里潜意识认为这种做法行不通的。（如果有大佬知道这是怎么回事，欢迎指点qwq）。
而且，这道题目的代码实现也非常非常地简单！
只要在原有的模板上做一点点更改就好了：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
struct Node{
int z,q,b;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
int dis[N];
bool vis[N];
priority_queue<Node>pq;
vector<Node>v[N];
int mei[N];
int main(){
int t;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)v[i].clear();
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
v[x].push_back({y,1,i});
mei[i]=1;
}
for(int i=1;i<=n;i++)dis[i]=INT_MAX;
for(int i=1;i<=n;i++)vis[i]=0;
pq.push({1,0,0});
int mx=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].z;
if(dis[to]>dis[k]+1){
dis[to]=dis[k]+1;
if(!vis[to])pq.push({to,dis[to],0});
}else if(dis[to]==dis[k]+1){
mx=max(mx,v[k][i].q+1);
mei[v[k][i].b]=v[k][i].q+1;
}
}
}
if(mx<=k){
cout<<"Yes\n";
for(int i=1;i<=m;i++)cout<<mei[i]<<" ";
cout<<'\n';
}else cout<<"No\n";
}
return 0;
}
我不会告诉你我调了半个小时就因为
if(!vis[k])pq.push({to,dis[to],0});
并且，可喜可贺的是在我调错的时候，我重新搞懂了这个思路，我明天来分析它！
好吧。我突然奋发图强了。所以我今天晚上就来分析它。
这个题解的楼主给你的感觉是：四两拨千斤。
但是实际上它很复杂。接下来我会从两个角度去分析：
一.文字本身
这句话看似普通又平常，但是想到它其实并不容易哦。
当你一开始做的时候，需要给每条边去赋值。你可能就得想：欸，我是要赋值最大值还是要赋值最小值，或者是中间值？（甚至如果你想的偏一点，你甚至可能根本想不出要赋值，可能回去想一些乱七八糟的方法，构造题本身就很容易很容易跑偏）
有一个突破口可以（更容易）想到它：
当k只能等于1，那么就直接赋值为1，然后融入一部分最短路计数的代码，去看有没有相同值。
这部分做完之后，你再去看接下来怎么做，就会更容易联想到。
接下来的部分我会从代码的角度去分析：
我上面的那版代码，是我已经更具这份题解提供的代码修改过的。
我现在将两份代码（我原来的和我现在的）进行对比。
现在的：
for(int i=0;i<v[k].size();i++){
int to=v[k][i].z;
if(dis[to]>dis[k]+1){
dis[to]=dis[k]+1;
if(!vis[to])pq.push({to,dis[to],0});
}else if(dis[to]==dis[k]+1){
mx=max(mx,2);
mei[v[k][i].b]=2;
}
}
原来的：
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])pq.push({to,dis[to],0});
}else if(dis[to]==dis[k]+len){
mx=max(mx,len+1);
mei[v[k][i].b]=len+1;
v[k][i].q=len+1;
}
}
接下来，我们一处对比一处对比地分析一下：
1.我将len变量删除了
并且把要加的len改成了"+1"。
这是因为，在dijkstra中，每条边能够对它所连接的点进行更新的机会永远都只有一次。
(因为每个点在Dijkstra里面也只会被遍历一次）
而第一次被遍历时，这条边的初始值也只能是1。
2.直接填写2
这边的逻辑和上面的逻辑是一样的。直接增加1就好了。
虽然我前面那些都写得很简单很轻松，但是其实头脑风暴了很久。
所以在这里得建议是：大家做完一道题之后可以去看看题解写的代码。有一些代码写的简短漂亮，那么它背后的思路可能也更好。
我当时发现后面可以直接填2得时候我都惊呆了。好妙得构造啊。
这道题我一直没有注意道德是：在dijkstra中，每条边只会进行一次遍历（单向边哦）。
不过这个也是只在模板上进行更改，并没有与算法进行美妙的联动。但是思想上有提升。
所以网没办法更新qwq。
好吧，我们看下一题吧。
五一新学了最小生成树。八级要考。先过一点最小生成树。
二.最小生成树
例题：买礼物
先说做法，再说想法。
做法：有优惠，一件礼物作为一个顶点，价格为边。建立零点，将零点与其他每个顶点连边，代表原价购买此商品。
由于在熟悉，所以prim和kruskal都会拿出来弄一遍。
prim:
#include<bits/stdc++.h>
using namespace std;
//prim
const int N=5e2+5;
struct Node{
int z,q;
friend bool operator < (Node a,Node b){
return a.q>b.q;
}
};
vector<Node>v[N];
priority_queue<Node>pq;
int dis[N];
bool vis[N];
int main(){
int a,b;
cin>>a>>b;
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int x;
cin>>x;
if(x==0)continue;
v[i].push_back({j,x});
}
}
for(int i=1;i<=b;i++){
v[0].push_back({i,a});
v[i].push_back({0,a});
}
for(int i=0;i<=b;i++)dis[i]=INT_MAX;
dis[0]=0;
pq.push({0,0});
while(!pq.empty()){
Node sum=pq.top();
pq.pop();
int k=sum.z;
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]>len&&!vis[to]){
dis[to]=len;
pq.push({to,dis[to]});
}
}
}
int ans=0;
for(int i=1;i<=b;i++)ans+=dis[i];
cout<<ans;
return 0;
}
在写prim的时候，我发现了一点比较有意思的事情。
我将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]>len&&!vis[to]){
dis[to]=len;
vis[to]=1;
pq.push({to,dis[to]});
}
}
如果加在了这里，那么如果后续我还能用别的边来优化dis，就优化不到了。
当时居然没注意，随意改了一下酿成大错qwq。
接下来是kruskal的版本。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
struct Node{
int x,y,z;
}node[N];
int c[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
int f(int x){
return (x==c[x])?x:c[x]=f(c[x]);
}
typedef long long ll;
int main(){
int a,b;
cin>>a>>b;
int n=0;//总共有多少条边
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
int xx;
cin>>xx;
if(xx==0)continue;
node[++n]={i,j,xx};
}
}
for(int i=1;i<=b;i++)node[++n]={0,i,a};
sort(node+1,node+1+n,cmp);
for(int i=0;i<=b;i++)c[i]=i;
ll ans=0;
for(int i=1;i<=n;i++){
int xx=node[i].x,yy=node[i].y;
if(f(xx)!=f(yy)){
ans+=node[i].z;
c[f(xx)]=f(yy);
}
}
cout<<ans;
return 0;
}
分析：
1.如何分析这道题目需要用到最小生成树
分析这个问题，先需要想到，这是一道和图论相关的问题。
如何将一个实际问题转化成为图。或者说如何识别有“图”。
它有点之间的关系。点i和点j之间的联系就是k[i][j]。
那么这个联系就可以变成边。
想在图论相关的题目中找”最小“。那么一般考虑：最短路，最小生成树，树形dp(我对树形dp不太了解，但应该也是相关）。
然后再看，这道题目需要求取整个图的所有边权。比较容易想到最小生成树。
最后分析复杂度：一共有n*n条边。大约2e5。可以支撑的起O(mlogn)的时间复杂度。
2.使用prim更好还是使用kruskal更好。
稠密图。推荐使用prim。
找最小生成树。再计算出点s到点t的最大值即可。
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+4;
struct Node{
int x,y,z;
}node[N];
struct Node1{
int zz,q;
};
vector<Node1>v[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
int c[N];
int f(int x){
return (x==c[x])?x:c[x]=f(c[x]);
}
bool vis[N];
int dis[N];
void dfs(int x){
for(int i=0;i<v[x].size();i++){
int to=v[x][i].zz;
int len=v[x][i].q;
if(!vis[to]){
vis[to]=1;
dis[to]=max(len,dis[x]);
dfs(to);
}
}
}
int main(){
int n,m,s,t;
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)cin>>node[i].x>>node[i].y>>node[i].z;
sort(node+1,node+1+m,cmp);
for(int i=1;i<=n;i++)c[i]=i;
int ans=0;
for(int i=1;i<=m;i++){
int p=f(node[i].x),q=f(node[i].y);
if(p==q)continue;
v[p].push_back({q,node[i].z});
v[q].push_back({p,node[i].z});
ans=max(ans,node[i].z);
c[f(p)]=f(q);
}
dfs(s);
cout<<dis[t];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+4;
struct Node{
int x,y,z;
}node[N];
bool cmp(Node a,Node b){
return a.z<b.z;
}
int c[N];
int f(int x){
return (x==c[x])?x:c[x]=f(c[x]);
}
bool vis[N];
int main(){
int n,m,kk;
cin>>n>>m>>kk;
for(int i=1;i<=m;i++)cin>>node[i].x>>node[i].y>>node[i].z;
sort(node+1,node+1+m,cmp);
for(int i=1;i<=n;i++)c[i]=i;
int ans=0;
int sum=0;
if(kk==n){
cout<<0;
return 0;
}
for(int i=1;i<=m+1;i++){
if(i==m+1)break;
int p=f(node[i].x),q=f(node[i].y);
if(p==q)continue;
c[f(p)]=f(q);
ans+=node[i].z;
sum++;
if(sum==n-kk){
cout<<ans;
return 0;
}
}
cout<<"No Answer";
return 0;
}
这里空空如也
有帮助，赞一个