devbox
秋刀鱼在做梦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

寒假“最小生成树”题解_scratch如何出一道关于最小生成树的题目

作者：秋刀鱼在做梦 | 2024-07-27 17:49:23

赞

踩

scratch如何出一道关于最小生成树的题目

1、P3366 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数Xi​,Yi​,Zi​，表示有一条长度为 Zi​ 的无向边连接结点 Xi​,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1复制

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1复制

7

说明/提示

数据规模：

对于 20% 的数据，N≤5，M≤20。

对于 40% 的数据，N≤50，M≤2500。

对于 70% 的数据，N≤500，M≤10^4。

对于 100% 的数据：1≤N≤5000，1≤M≤2×10^5，1≤Zi​≤10^4。

样例解释：

所以最小生成树的总边权为 2+2+3=7。

 题解：本题可以用kruskal来做，按每条边的权值从小到大排序，从头开始一条一条边放进去，如果放进去树形成了环那么就跳过该条边（判断是否形成环，可以用并查集来实现，首先初始化各个顶点的父亲为自己，在放边的时候如果两个顶点都在同一个并查集里面（即父亲相等），那么放这条边就会形成环），每次放进一条边，就要把这条边的两个顶点合并到一个集合里面，直到放满n-1（n为顶点的个数）条边，最小生成树就形成了。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define M 200010
  4. #define N 5010
  5. int n,m,fa[N],cnt=0,sum=0;
  6. struct tree{
  7. 	int fir;
  8. 	int nxt;
  9. 	int w;
  10. }p[M];
  11. bool cmp(struct tree a,struct tree b){//按边的权值升序排列 
  12. 	if(a.w<b.w) return true;
  13. 	else return false;
  14. } 
  15. int find(int t){//找父亲 
  16. 	if(fa[t]==t) return t;
  17. 	return fa[t]=find(fa[t]);//压缩路径 
  18. }
  19. int main(){
  20. 	scanf("%d%d",&n,&m);
  21. 	for(int i=1;i<=n;i++)//初始化父亲 
  22. 	  fa[i]=i;
  23. 	for(int i=1;i<=m;i++)
  24. 	  scanf("%d%d%d",&p[i].fir,&p[i].nxt,&p[i].w);
  25. 	sort(p+1,p+m+1,cmp);
  26. 	for(int i=1;i<=m;i++){
  27. 		int fa1=find(p[i].fir),fa2=find(p[i].nxt);
  28. 		if(fa1==fa2) continue;//两点在一个并查集内,就会组成环 
  29. 		sum+=p[i].w;
  30. 		cnt++;
  31. 		fa[fa1]=fa2;//已连接,所以要合并集合 
  32. 		if(cnt==n-1) break;
  33. 	}
  34. 	if(cnt==n-1)//n个点能连n-1条边即可 
  35. 	  printf("%d\n",sum);
  36. 	else
  37. 	  printf("orz\n");   
  38. }

2、P1195 口袋的天空

题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数 N，再给你 M 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 K 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入格式

第一行有三个数 N,M,K。

接下来 M 行每行三个数 X,Y,L，表示X云和 Y 云可以通过 L 的代价连在一起。

输出格式

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 K 个棉花糖，请输出 No Answer。

输入输出样例

输入 #1复制

3 1 2
1 2 1

输出 #1复制

1

说明/提示

对于 30% 的数据，N≤100，M≤10^3；

对于 100% 的数据，1≤N≤10^3，1≤M≤10^4，1≤K≤10，1≤X,Y≤N，0≤L<10^4。

 题解：要将n个云朵连接成k个棉花糖，就需要连接n-k根线，所以如果m即边的的数量少于n-k根的话那么就不可能组成k个棉花糖，大于等于n-k根即可组成k个棉花糖。因为反正必须要连接n-k根线，而且要总的连线代价最小，所以可以按每条连线的代价，从小到大选择n-k根线，对于每次选线也需用并查集确保不组成环，所以这其实就是kruskal。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define M 10010
  4. int fa[1010],sum,cnt;
  5. struct tree{
  6. 	int u;
  7. 	int v;
  8. 	int w;
  9. }e[M];
  10. bool cmp(struct tree a,struct tree b){//按边的权值升序排列 
  11. 	if(a.w<b.w) return true;
  12. 	else return false;
  13. } 
  14. int find(int t){//找父亲 
  15. 	if(fa[t]==t) return t;
  16. 	return fa[t]=find(fa[t]);//压缩路径 
  17. }
  18. int main(){
  19. 	int n,m,k;
  20. 	scanf("%d%d%d",&n,&m,&k);
  21. 	for(int i=1;i<=n;i++)//初始化父亲 
  22. 	  fa[i]=i;
  23. 	for(int i=1;i<=m;i++)
  24. 	  scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
  25. 	sort(e+1,e+m+1,cmp);
  26. 		for(int i=1;i<=m;i++){
  27. 		int fa1=find(e[i].u),fa2=find(e[i].v);
  28. 		if(fa1==fa2) continue;//两点在一个并查集内,就会组成环 
  29. 		sum+=e[i].w;
  30. 		cnt++;
  31. 		fa[fa1]=fa2;//已连接,所以要合并集合 
  32. 		if(cnt==n-k) break;
  33. 	}
  34. 	if(cnt==n-k)//n朵云朵要组成k个棉花糖，则需要连接n-k根线 
  35. 	  printf("%d\n",sum);
  36. 	else
  37. 	  printf("No Answer\n");   
  38. }

3、P2121 拆地毯

题目背景

还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

题目描述

会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示，其中 u 和 v 为地毯连接的两个关键区域编号，w 为这条地毯的美丽度。

由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留 K 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这 K 条地毯的美丽度之和最大为多少。

输入格式

第一行包含三个正整数 n、m、K。

接下来 m 行中每行包含三个正整数 u、v、w。

输出格式

只包含一个正整数，表示这 K 条地毯的美丽度之和的最大值。

输入输出样例

输入 #1复制

5 4 3
1 2 10
1 3 9
2 3 7
4 5 3

输出 #1复制

22

说明/提示

选择第 1、2、4 条地毯，美丽度之和为 10 + 9 + 3 = 22。

若选择第 1、2、3 条地毯，虽然美丽度之和可以达到 10 + 9 + 7 = 26，但这将导致关键区域 1、2、3 构成一个环，这是题目中不允许的。

1<=n,m,k<=100000

 题解：本题要拆除多余的地毯，但至少要使任意两点能相互到达且不形成环，最后还需要所剩美丽值最大。那么其实本题也就是一个反的最小生成树，通常的最小生成树都是让所和权值最小，而这就是让它最大，所以可以按权值（即美丽值）从大到小排列每条边，然后用kruskal的做法，在不组成环的前提下，从大到小放进k条边即可。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define N 100010
  4. int n,m,k,fa[N],cnt=0,sum=0;
  5. struct tree{
  6. 	int u;
  7. 	int v;
  8. 	int w;
  9. }e[N];
  10. bool cmp(struct tree a,struct tree b){//按边的权值升序排列 
  11. 	if(a.w>b.w) return true;
  12. 	else return false;
  13. } 
  14. int find(int t){//找父亲 
  15. 	if(fa[t]==t) return t;
  16. 	return fa[t]=find(fa[t]);//压缩路径 
  17. }
  18. int main(){
  19. 	scanf("%d%d%d",&n,&m,&k);
  20. 	for(int i=1;i<=n;i++)//初始化父亲 
  21. 	  fa[i]=i;
  22. 	for(int i=1;i<=m;i++)
  23. 	  scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
  24. 	sort(e+1,e+m+1,cmp);
  25. 	for(int i=1;i<=m;i++){
  26. 		int fa1=find(e[i].u),fa2=find(e[i].v);
  27. 		if(fa1==fa2) continue;//两点在一个并查集内,就会组成环 
  28. 		sum+=e[i].w;
  29. 		cnt++;
  30. 		fa[fa1]=fa2;//已连接,所以要合并集合 
  31. 		if(cnt==k) break;
  32. 	}
  33. 	  printf("%d\n",sum);
  34. }

4、P1991 无线通讯网

题目描述

国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络；

每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。

任意两个配备了一条卫星电话线路的哨所（两边都ᤕ有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。

收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距离 D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

输入格式

从 wireless.in 中输入数据第 1 行，2 个整数 S 和 P，S 表示可安装的卫星电话的哨所数，PP 表示边防哨所的数量。接下里 P 行，每行两个整数 x，y 描述一个哨所的平面坐标 (x, y)，以 km 为单位。

输出格式

输出 wireless.out 中

第 1 行，1 个实数 D，表示无线电收发器的最小传输距离，精确到小数点后两位。

输入输出样例

输入 #1复制

2 4
0 100
0 300
0 600
150 750

输出 #1复制

212.13

说明/提示

对于 20% 的数据：P = 2，S = 1

对于另外 20% 的数据：P = 4，S = 2

对于 100% 的数据保证：1≤S≤100，S < P ≤ 500，0 ≤ x,y ≤ 10000。

题解： 每个哨塔可以用卫星电话或者无线电连接，卫星电话的距离不限，而我们要找出用无线电连接的最短距离，并且所有哨塔需要用同一种无线电，并且保证任意两个哨塔都能相连，也就是使图连通。那么我们就可以依次把卫星电话给安排给哨塔距离相隔最远的几个，而其他哨塔就均用无线电，那么所有无限点最短距离，则取决于距离从大到小除去已安排卫星电话的哨塔后的第一个距离。所有哨塔相连需要p-1根线，s个卫星电话又可以组成s-1根线，那么我们就可以计算出任意所有点两两相隔的距离，然后按照距离从小到大防线，放到p-1-(s-1)根线时就是所有哨塔应该选择的无线电的最短距离。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int fa[510];
  4. struct tree{
  5. 	int u;
  6. 	int v;
  7. 	double w;
  8. }e[1000001];
  9. bool cmp(struct tree a,struct tree b){//按边的权值升序排列 
  10. 	if(a.w<b.w) return true;
  11. 	else return false;
  12. } 
  13. int find(int t){//找父亲 
  14. 	if(fa[t]==t) return t;
  15. 	return fa[t]=find(fa[t]);//压缩路径 
  16. }
  17. int main(){
  18. 	int s,p,zb[510][2],k=1,cnt=0;
  19. 	double ans;
  20. 	scanf("%d%d",&s,&p);
  21. 	for(int i=1;i<=p;i++)
  22. 	  fa[i]=i; 
  23. 	for(int i=1;i<=p;i++)
  24. 	  scanf("%d%d",&zb[i][0],&zb[i][1]);
  25. 	for(int i=1;i<=p;i++)//求出所有哨塔，两两之间的距离 
  26. 		for(int j=i+1;j<=p;j++){
  27. 		  e[k].u=i;
  28. 		  e[k].v=j;
  29. 		  e[k++].w=sqrt((zb[i][0]-zb[j][0])*(zb[i][0]-zb[j][0])+(zb[i][1]-zb[j][1])*(zb[i][1]-zb[j][1]));
  30. 		}  
  31. 	sort(e+1,e+k+1,cmp);
  32. 	for(int i=1;i<=k;i++){
  33. 		int fa1=find(e[i].u),fa2=find(e[i].v);
  34. 		if(fa1==fa2) continue;//两点在一个并查集内,就会组成环 
  35. 		ans=e[i].w;
  36. 		cnt++;
  37. 		fa[fa1]=fa2;//已连接,所以要合并集合 
  38. 		if(cnt==p-1-(s-1)) break;//s个卫星电话可连接s-1线,找到所有需要连接无线电哨塔的数量-卫星电话已连接数量,即可停止 
  39. 	}
  40. 	printf("%.2lf",ans);	
  41. }

5、P2872 [USACO07DEC]Building Roads S

题目描述

Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.

Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.

给定 n 个点的坐标，第 i 个点的坐标为 (xi​,yi​)，这 n 个点编号为 1 到 n。给定 m 条边，第 i 条边连接第 ui​ 个点和第 vi​ 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Two space-separated integers: Xi and Yi

* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.

第一行两个整数 n,m 代表点数与边数。
接下来 n 行每行两个整数 xi​,yi​ 代表第 i 个点的坐标。
接下来 m 行每行两个整数 ui​,vi​ 代表第 i 条边连接第 ui​ 个点和第 vi​ 个点。

输出格式

* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.

一行一个实数代表添加的边的最小长度，要求保留两位小数，为了避免误差， 请用 64 位实型变量进行计算。

输入输出样例

输入 #1复制

4 1
1 1
3 1
2 3
4 3
1 4

输出 #1复制

4.00

说明/提示

数据规模与约定

对于 100% 的整数，1≤n,m≤1000，1≤xi​,yi​≤10^6，1≤ui​,vi​≤n。

说明

Translated by 一只书虫仔。

 题解：先将所有点两两之间的所有距离都算出来,一样用kruskal的方式,按照距离从小到大放边,组成最小生成树,只不过有m条边也确定,那么首先将m条边的两个顶点合并到一个集合,到时候方便判断环时,那么就可以跳过该条边,因为已经有了m条已确定,那么当放到n-1-m条边时即可停止循环,那么整个最小生成树也形成了.

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int fa[1010];
  4. struct tree{
  5. 	int u;
  6. 	int v;
  7. 	double w;
  8. }e[5000100];
  9. bool cmp(struct tree a,struct tree b){//按边的权值升序排列 
  10. 	if(a.w<b.w) return true;
  11. 	else return false;
  12. } 
  13. int find(int t){//找父亲 
  14. 	if(fa[t]==t) return t;
  15. 	return fa[t]=find(fa[t]);//压缩路径 
  16. }
  17. int main(){
  18. 	int n,m,zb[1000][2],k=1,cnt=0;
  19. 	double sum=0;
  20. 	scanf("%d%d",&n,&m);
  21. 	for(int i=1;i<=n;i++)
  22. 	  fa[i]=i;
  23. 	for(int i=1;i<=n;i++)
  24. 	  scanf("%d%d",&zb[i][0],&zb[i][1]);
  25. 	while(m--){
  26. 		int u,v;
  27. 		scanf("%d%d",&u,&v);
  28. 		fa[find(u)]=find(v);//合并 
  29. 	} 
  30. 	for(int i=1;i<=n;i++)//求出所有点，两两之间的距离 
  31. 		for(int j=i+1;j<=n;j++){
  32. 		  e[k].u=i;
  33. 		  e[k].v=j;
  34. 		  e[k++].w=sqrt((double)(zb[i][0]-zb[j][0])*(zb[i][0]-zb[j][0])+(double)(zb[i][1]-zb[j][1])*(zb[i][1]-zb[j][1]));
  35. 		}  
  36. 	sort(e+1,e+k+1,cmp);
  37. 	for(int i=1;i<=k;i++){
  38. 		int fa1=find(e[i].u),fa2=find(e[i].v);
  39. 		if(fa1==fa2) continue;//两点在一个并查集内,就会组成环 
  40. 		sum+=e[i].w;
  41. 		cnt++;
  42. 		fa[fa1]=fa2;//已连接,所以要合并集合 
  43. 		if(cnt==n-1-m) break;//m条边已确定,所以减去
  44. 	}
  45. 	printf("%.2lf",sum);    
  46. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/891123
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号