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

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

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

比赛链接

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

kruskal算法的思想是贪心地尝试加入边权最小的边。众所周知，联通 $n$ 个点最少需要 $n-1$ 条边，因为我们每加入一条边，互不连通的点的集合就减少 $1$。在此之上加入的任何一条边对连通性来说都是没有用的。所以在每次都能合并两个不连通的点的集合的前提下 贪心地尝试加入边权小的边，加入 $n-1$ 个边后就可以将所有点联通起来，同时加入的边的边权之和最小。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$ 条边时，直接输出这条边即可。

整段就不粘了，大部分与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}$）。这样的话，我们要将所有点加入到一个集合中，实际上就是在跑最小生成树。

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$ 走到点 $t$ 的最短“距离”，这个距离表示的是路径上的最大边权。

当成最小生成树的话，使用prim算法，相当于求 将 $t$ 加入生成树时加入的边的边权。使用kruskal也可以，不过需要分别记录一下 $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$ 就是这个矩形的右下角。

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

但是题目输出要求很刁钻。我们要按字典序输出所有可能的顺序。考虑到拓扑排序的时候，我们有一个队列用来存储当前可以用来删除的点，也就是说，对一个队列，我们可以选择其中任意一个点进行删点操作，删点的顺序其实就是图层的顺序，因此我们按从小到大的顺序来删点，这里其实就有些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序和拓扑排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---