郑州大学2024年寒假训练 Day5:生成树,DFS序和拓扑排序

2024-02-20 04:44

本文主要是介绍郑州大学2024年寒假训练 Day5:生成树,DFS序和拓扑排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

还是比较简单的,A-F是生成树,GHI是拓扑排序。最后三题出的是真好。

比赛链接

求解最小生成树的算法有两个,一个是kruskal 克鲁斯卡尔 算法,一个是prim 普利姆 算法。这两个都是贪心思想,只是贪的东西不一样。

kruskal算法的思想是贪心地尝试加入边权最小的边。众所周知,联通 n n n 个点最少需要 n − 1 n-1 n1 条边,因为我们每加入一条边,互不连通的点的集合就减少 1 1 1。在此之上加入的任何一条边对连通性来说都是没有用的。所以在每次都能合并两个不连通的点的集合的前提下 贪心地尝试加入边权小的边,加入 n − 1 n-1 n1 个边后就可以将所有点联通起来,同时加入的边的边权之和最小。kruskal算法的实现只需要对边按边权排序,并可以同时查询边的两个端点,还要查询两个点的连通性。所以前面只需要一个结构体来存储然后sort一下就可以了,后者使用一个并查集来维护即可。

prim算法的思想是贪心地将当前没有加入生成树的距离生成树最近的点加入生成树,和dijkstra不能说完全相同,只能说一模一样,只不过到源点的距离数组的含义变成了到生成树的距离。至于为什么这么贪心是对的?我们假设已经知道最后生成树是什么了,那么剩下的点肯定是和其他剩下的点合并成一个一个的点的集合,然后每个集合都有一条边接到生成树上,那要把这个点所在集合合并到生成树上时也必须走一条边,假如我们现在合并时不选这个最短边,那选其他边一定是不优的,因为边权都变大了。prim算法和dijkstra一模一样,堆优化也是一模一样,所以需要堆,链式前向星,再开一个距离数组就ok了。

写法上如果只是要实现求解最小生成树,显然前者码量大大小于后者,如果还要一些其他的图论的处理,prim的写法就会比较有优势了。


A

思路:

裸生成树板子

code:

prim算法(vis数组可写可不写,因为就算不写,取出过的点之后也不可能入堆了。)

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=105;
const int inf=1e9;
typedef long long ll;inline int read(){int ans=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){ans=(ans<<3)+(ans<<1)+(ch^48);ch=getchar();}return ans*f;
}int n,m;int head[maxn],cnt;
struct edge{int v,w,nxt;
}e[maxn*maxn];
void add(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;
}int main(){while(n=read()){m=n*(n-1)/2;for(int i=1;i<=n;i++)head[i]=0;cnt=0;for(int i=1,u,v,w;i<=m;i++){u=read();v=read();w=read();add(u,v,w);add(v,u,w);}vector<bool> vis(n+1);vector<int> d(n+1,inf);ll ans=0;priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > h;h.push(make_pair(0,1));d[1]=0;while(!h.empty()){int u=h.top().second;h.pop();if(vis[u])continue;else {vis[u]=true;ans+=d[u];}for(int i=head[u],v,w;i;i=e[i].nxt){v=e[i].v;w=e[i].w;if(vis[v])continue;if(d[v]>w){d[v]=w;h.push(make_pair(d[v],v));}}}printf("%lld\n",ans);}return 0;
}

B

思路:

不是很裸的生成树也是裸生成树。我们发现一开始有些边直接就给你了,这意味着我们可以没有代价地把它们加入生成树,所以我们直接把送给我们的边的边权置为0,之后就是裸生成树了。

code:

kruskal算法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=105;
const int inf=1e9;
typedef long long ll;inline int read(){int ans=0,f=1;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){ans=(ans<<3)+(ans<<1)+(ch^48);ch=getchar();}return ans*f;
}int n,m;struct edge{int u,v,w;bool operator<(edge x){return w<x.w;}
}e[maxn*maxn];int f[maxn];
inline int findf(int x){if(f[x]==x)return x;else return f[x]=findf(f[x]);
}
inline void merge(int a,int b){int fa=findf(a),fb=findf(b);f[fb]=fa;
}
inline bool query(int a,int b){return findf(a)==findf(b);
}int main(){while(n=read()){m=n*(n-1)/2;for(int i=1;i<=n;i++)f[i]=i;for(int i=1,st;i<=m;i++){e[i].u=read();e[i].v=read();e[i].w=read();st=read();if(st)e[i].w=0;}sort(e+1,e+m+1);ll ans=0;for(int i=1;i<=m;i++)if(!query(e[i].u,e[i].v)){ans+=e[i].w;merge(e[i].u,e[i].v);}printf("%lld\n",ans);}return 0;
}

C

思路:

裸生成树,没什么好说的。代码直接看B题的,不粘了,太占篇幅。


D

思路:

还是裸生成树,只不过我们需要输出最小生成树中最大的边权。考虑到在kruskal算法中,我们是贪心地从小边权到大边权 进行加边,因此最大边权一定是最后加入的,所以我们跑一边kruskal算法,然后当加入第 n − 1 n-1 n1 条边时,直接输出这条边即可。

整段就不粘了,大部分与B题的一致,最后不同的片段如下:

int cnt=0;
for(int i=1;i<=m;i++){if(!query(e[i].u,e[i].v)){cnt++;merge(e[i].u,e[i].v);if(cnt==n-1){printf("%d %d\n",cnt,e[i].w);return 0;}}
}

E

思路:

把每个物品看作一个点,两个点的边权就是买了其中一个物品时,另一个物品的价值(也就是 K i , j K_{i,j} Ki,j)。这样的话,我们要将所有点加入到一个集合中,实际上就是在跑最小生成树。

code:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=505;
const int maxm=250005;int A,n,m;
struct edge{int u,v,w;bool operator<(edge x){return w<x.w;}
}e[maxm<<1];int f[maxn];
inline int findf(int x){return (f[x]==x)?x:f[x]=findf(f[x]);
}
inline void merge(int a,int b){int fa=findf(a),fb=findf(b);f[fb]=fa;
}
inline bool query(int a,int b){return findf(a)==findf(b);
}int main(){cin>>A>>n;m=0;for(int i=1;i<=n;i++)f[i]=i;for(int i=1,w;i<=n;i++){for(int j=1;j<=n;j++){cin>>w;if(w){e[++m].u=i;e[m].v=j;e[m].w=w;}}}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){e[++m].u=i;e[m].v=j;e[m].w=A;}sort(e+1,e+m+1);int ans=0;for(int i=1;i<=m;i++){if(!query(e[i].u,e[i].v)){ans+=e[i].w;merge(e[i].u,e[i].v);}}cout<<A+ans<<endl;return 0;
}

F

P1396 营救

思路:

这题当成最短路还是最小生成树都可以,毕竟prim和kruskal写法是一模一样的。

当成最短路来看的话,相当于求 s s s 走到点 t t t 的最短“距离”,这个距离表示的是路径上的最大边权。

当成最小生成树的话,使用prim算法,相当于求 将 t t t 加入生成树时加入的边的边权。使用kruskal也可以,不过需要分别记录一下 s , t s,t s,t 所在点集,合并的时候检查一下这条边是否合并了两个集合,如果是,那么这个边就是最大边权。

code:

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1e4+5;
const int maxm=2e4+5;
const int inf=1e9;int n,m,S,T;
bool vis[maxn];
int d[maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > h;int head[maxn],cnt;
struct edge{int v,w,nxt;
}e[maxm<<1];
void add(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;
}int main(){cin>>n>>m>>S>>T;for(int i=1,u,v,w;i<=m;i++){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}for(int i=1;i<=n;i++)d[i]=inf;d[S]=0;h.push(make_pair(d[S],S));while(!h.empty()){int u=h.top().second;h.pop();if(vis[u])continue;else vis[u]=true;for(int i=head[u],v,w;i;i=e[i].nxt){v=e[i].v;w=e[i].w;if(vis[v])continue;if(d[v]>max(d[u],w)){d[v]=max(d[u],w);h.push(make_pair(d[v],v));}}}cout<<d[T]<<endl;return 0;
}

G

P1038 [NOIP2003 提高组] 神经网络

思路:

这题有点好,就是有点坑。提前避坑:

  1. 输入渠道不需要减去阈值
  2. 输入渠道有可能同时是输出渠道

我们要知道某个点的值,首先必须知道指向它的所有点的值,然后根据指向它的所有点来算这个点。反过来,如果我们可以算一个点,就把它的贡献算出来给到指向的所有点。由于拓扑排序的访问顺序就是在访问一个点之前一定可以访问到所有它的前置节点,因此我们跑一遍拓扑排序,边跑边把当前点的贡献算出来给到所有后继节点,就得到了所有点的值。

由于是某个点的属性,每个点只需要减去一次就行,所以我们直接提前把阈值当作贡献先减到每一个点上。因为输入点不需要减去阈值,而我们需要输出所有输出点。因此我们用一个入度数组和一个出度数组记录每个点的入度和出度,输入点的入度为0,初始加入点的时候直接把它们的阈值清零,输出点的出度为0,最后检查一遍输出即可。

code:

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=105;
const int maxm=10005;
typedef long long ll;int n,m;
int in[maxn],ot[maxn];
ll val[maxn],U[maxn];int head[maxn],cnt;
struct edge {int v,w,nxt;
}e[maxm];
void add(int u,int v,int w){in[v]++;ot[u]++;e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;
}int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>val[i]>>U[i];val[i]-=U[i];}for(int i=1,u,v,w;i<=m;i++){cin>>u>>v>>w;add(u,v,w);}queue<int> q;for(int i=1;i<=n;i++)if(!in[i]){q.push(i);val[i]+=U[i];}while(!q.empty()){int u=q.front();q.pop();for(int i=head[u],v,w;i;i=e[i].nxt){v=e[i].v;w=e[i].w;val[v]+=max(val[u],0ll)*w;in[v]--;if(!in[v]){q.push(v);}}}bool f=false;for(int i=1;i<=n;i++)if(!ot[i] && val[i]>0){printf("%d %lld\n",i,val[i]);f=true;}if(!f)puts("NULL");return 0;
}

H

P1983 [NOIP2013 普及组] 车站分级

思路:

转化一下题意的话,其实就是一列列车包含 所有级别大于这列列车经过的最小级别站点 的站点。换句话说,就是没有包含的站点等级一定小于包含的站点。我们把每个站点看作图上的一个点,根据上面说的给包含的点向不包含的点连接一条有向边,表示等级大小。显然如果我们按顺序给点标等级,那么一个点的前置节点必须在这个点之前被标记到。

有了这个关系,就可以考虑拓扑排序了,而找最少的站点等级数就是找这个有向无环图上最长的那个链,所以我们可以从入度为0的点开始拓扑排序,给一个点记录一下到这个点最长的链的长度,然后我们每取出一个点的时候就尝试给它的所有后继节点的记录值更新一下(怎么感觉有点DP)。由于是拓扑排序,我们要取出一个点的时候,它的所有前置节点一定访问完了,这个点的值也不会再更新了。

由于我们可能会大量重复加边导致爆掉数组空间,所以需要标记每条边,防止重复加边。

code:

#include <iostream>
#include <cstdio>
#include <set>
#include <queue>
using namespace std;
const int maxn=1005;int n,m;bool ise[maxn][maxn];
int head[maxn],cnt;
int in[maxn];
struct edge{int v,nxt;
}e[maxn*maxn];
void add(int u,int v){in[v]++;e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}int idx[maxn],ans;int main(){cin>>n>>m;for(int i=1,s,t,lst;i<=m;i++){cin>>s>>lst;set<int> S1,S2;S1.insert(lst);for(int j=2;j<=s;j++){cin>>t;S1.insert(t);for(int k=lst+1;k<t;k++)S2.insert(k);lst=t;}for(auto u:S1)for(auto v:S2)//S1中的车站级别都高于S2 if(!ise[u][v]){add(u,v); ise[u][v]=true;}}queue<int> q;for(int i=1;i<=n;i++)if(!in[i]){q.push(i);idx[i]=1;ans=1;}while(!q.empty()){int u=q.front();q.pop();for(int i=head[u],v;i;i=e[i].nxt){v=e[i].v;in[v]--;if(!in[v]){idx[v]=idx[u]+1;ans=max(ans,idx[v]);q.push(v);}}}cout<<ans<<endl;return 0;
}

I

P2741 [USACO4.4] 重叠的图像Frame Up

思路:

好题。

先考虑怎么找到某个字符组成的矩形。因为题目保证了每种字符的矩形只有一个,而且每条边都至少会露出来一个这种字符,所以我们记录一下这种字符所有出现的 x , y x,y x,y 值,最小的 x , y x,y x,y 就是这个矩形的左上角端点,最大的 x , y x,y x,y 就是这个矩形的右下角。

找到矩形后,我们就可以枚举矩形的边 上面的字符了。如果某个位置被替换成其他字符,就说明这个字符的图层低于这个其他字符,我们就得到了一组关系。把每个字符看成一个点,用有向边来表示关系,之后跑拓扑排序即可。至于谁指向谁,主要是看题目,被指向的点删除的晚。这个题里,我们希望删点的顺序就是图层顺序。最后输出的点就是图层在最上面的点,也就是说图层在下面的点比图层在上面的点删的早,所以我们由其他字符代表的点指向这个字符代表的点。

但是题目输出要求很刁钻。我们要按字典序输出所有可能的顺序。考虑到拓扑排序的时候,我们有一个队列用来存储当前可以用来删除的点,也就是说,对一个队列,我们可以选择其中任意一个点进行删点操作,删点的顺序其实就是图层的顺序,因此我们按从小到大的顺序来删点,这里其实就有些dfs的思想了。我们进行删点,然后向下走,返回的时候还原现场,再按顺序向下删点。因为我们dfs走到的所有状态都是会输出的,没有无效状态,而且题目既然要求我们输出字典序,这就说明输出字典序不会超时,而和它时间复杂度相同的dfs也肯定不会超时。

考虑怎么按大小顺序删点,如果用队列的话,由于要枚举其中的某些点,而STL里的队列只能访问开头和结尾的元素,所以我们需要手写队列。为了保证队列有序我们在每次加入点后对所有点排序,或者直接暴力寻找字典序最小的点。我们在选取一个点删掉后,这个位置就出现了一个空洞。这就需要用标记数组标记被删掉的点,然后这还会导致不保存原来的状态的话回溯起来非常困难。

考虑到dfs的层数很浅,而且点的个数也不多,我们每个状态直接用容器来保存队列里的所有点,为了维护有序性,我选择使用set。每次我们枚举set中的点,因为set本身元素就是有序的,所以我们取出来的点顺序就是有序的,删去取出来的点,然后用一个临时set存储下一个状态的队列中的所有点(不用删当前set的点,删的是要传给下一个状态的set中的点,当前状态能删的点是固定的,我们删不同的点影响的是转移之后的状态是什么),这样上面的问题都可以得到解决。

实际上这里的实现方法很多,可以去洛谷的题解区长长见识。

code:

#include <iostream>
#include <cstdio>
#include <set>
#include <cstring>
using namespace std;
const int maxn=35;int n,m;
string mp[maxn];
set<int> X[maxn],Y[maxn];//每个字母出现的xy值 bool ise[maxn][maxn];
int head[maxn],cnt;
int in[maxn];
struct edge{int v,nxt;
}e[maxn*maxn];
void add(int u,int v){if(!ise[u][v])ise[u][v]=true;else return;in[v]++;e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}int num;
int tmp[maxn];
void dfs(int x,set<int> q){//选第x个位置 if(x==num+1){for(int i=1;i<=num;i++)printf("%c",'A'+tmp[i]);puts("");return;}set<int> nq=q;for(auto u:q){tmp[x]=u;nq.erase(u);for(int j=head[u],v;j;j=e[j].nxt){v=e[j].v;in[v]--;if(!in[v]){nq.insert(v);}}dfs(x+1,nq);for(int j=head[u],v;j;j=e[j].nxt){v=e[j].v;if(!in[v]){nq.erase(v);}in[v]++;}nq.insert(u);}
}int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>mp[i];mp[i]=" "+mp[i];}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]!='.'){X[mp[i][j]-'A'].insert(i);Y[mp[i][j]-'A'].insert(j);}for(int i=0,x1,x2,y1,y2;i<26;i++){if(X[i].empty())continue;num++;x1=*X[i].begin();y1=*Y[i].begin();//左上角点 x2=*X[i].rbegin();y2=*Y[i].rbegin();//右下角点 set<int> S;for(int j=y1;j<=y2;j++){if(mp[x1][j]!='A'+i)S.insert(mp[x1][j]-'A');if(mp[x2][j]!='A'+i)S.insert(mp[x2][j]-'A');}for(int j=x1;j<=x2;j++){if(mp[j][y1]!='A'+i)S.insert(mp[j][y1]-'A');if(mp[j][y2]!='A'+i)S.insert(mp[j][y2]-'A');}for(auto x:S)add(i,x);}set<int> q;for(int i=0;i<26;i++)if(X[i].size() && !in[i])q.insert(i);dfs(1,q);return 0;
}

这篇关于郑州大学2024年寒假训练 Day5:生成树,DFS序和拓扑排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/727088

相关文章

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D