Kuangbin Flying 6最小生成树专题

先说算法：解释算法思想，可以直接从底下的代码复制作为模版

1.Prim。http://baike.baidu.com/link?url=A_L0v3P9Fqk_cmIGZYzA_hFRSOcCGHF8HYISu8HPjmihFhZ_V22oB3agYXCOYI2dY-SELII_ACQaEh5wK7Bmxq

2.Kruskal。http://baike.baidu.com/view/247951.htm


相信百度百科比我讲得绝对好多了。

图论最主要是建图的思想，然后就是上bin神的模版


A - Jungle Roads

裸最小生成树。注意：输入的时候用cin或者%s输入，不要读取字符之间的空格作为分隔符（有可能输入的时候输入的多个空格作为间隔导致出错）。无论用Prim还是Kruskal简直秒杀。

#include <cstdio>  
#include <algorithm>  
#include <iostream>  
#include <cstring>  
#include <cmath>  
#include <cstdlib>  
#include <string>  
#include <map>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <cctype>  
using namespace std;  

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30

const int maxn=200;
const int maxm=20000;
int F[maxn];
struct Edge
{
	int u,v,w;
}edge[maxm];

int tol;
void addedge(int u,int v,int w)
{
	edge[tol].u=u;
	edge[tol].v=v;
	edge[tol++].w=w;
}

bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}

int find(int x)
{
	if (F[x]==-1) return x;
	return F[x]=find(F[x]);
}

int Kruskal(int n)
{
	Fill(F,-1);
	sort(edge,edge+tol,cmp);
	int cnt=0;
	int ans=0;
	for(int i=0;i<tol;i++)
	{
		int u=edge[i].u;
		int v=edge[i].v;
		int w=edge[i].w;
		int t1=find(u);
		int t2=find(v);
		if (t1!=t2)
		{
			ans+=w;
			F[t1]=t2;
			cnt++;
		}
		if (cnt==n-1) break;
	}
	// (cnt<n-1) return -1;
	return ans;
}

int main()
{
	//input; 
	int i,n,m,x,y,z,ans,t,j,k;
	char s[10],s0[10];
	while(cin>>n,n)
	{
		ans=tol=0;
		For2(i,1,n-1)
		{
			scanf("%s%d",s,&t);
			if (t==0) continue;
			while(t--)
			{
				scanf("%s%d",s0,&k);
				addedge(s[0]-'A',s0[0]-'A',k);
				addedge(s0[0]-'A',s[0]-'A',k);
			}
			//addedge(y,x,z);
		}
		ans=Kruskal(n);
		cout<<ans<<endl;
	}
	return 0;
}

B - Networking

注意点与点之间是多重边的问题。所以边的初始化应该是无穷大，之后每次选择最小的（Prim）。Kruskal建图更加方便，不管三七二十一全部扔进去排序，然后并查***自动帮助我们去重的。建图之后裸最小生成树

#include <cstdio>  
#include <algorithm>  
#include <iostream>  
#include <cstring>  
#include <cmath>  
#include <cstdlib>  
#include <string>  
#include <map>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <cctype>  
using namespace std;  

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30

const int maxn=200;
const int maxm=20000;
int F[maxn];
struct Edge
{
	int u,v,w;
}edge[maxm];

int tol;
void addedge(int u,int v,int w)
{
	edge[tol].u=u;
	edge[tol].v=v;
	edge[tol++].w=w;
}

bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}

int find(int x)
{
	if (F[x]==-1) return x;
	return F[x]=find(F[x]);
}

int Kruskal(int n)
{
	Fill(F,-1);
	sort(edge,edge+tol,cmp);
	int cnt=0;
	int ans=0;
	for(int i=0;i<tol;i++)
	{
		int u=edge[i].u;
		int v=edge[i].v;
		int w=edge[i].w;
		int t1=find(u);
		int t2=find(v);
		if (t1!=t2)
		{
			ans+=w;
			F[t1]=t2;
			cnt++;
		}
		if (cnt==n-1) break;
	}
	if (cnt<n-1) return 0;
	return ans;
}

int main()
{
	//input; 
	int i,n,m,x,y,z,ans,t,j,k;
	char s[10],s0[10];
	while(cin>>n,n)
	{
		cin>>m;
		ans=tol=0;
		For2(i,1,m)
		{
			scanf("%d%d%d",&x,&y,&z);
			addedge(x,y,z);
			addedge(y,x,z);
		}
		ans=Kruskal(n);
		cout<<ans<<endl;
	}
	return 0;
}

C - Building a Space Station

给的是n个点的坐标以及以该点为坐标的球的半径。

建图：两个for循环，求出两个球球面的距离。先算出两个球心之间的距离，若该距离<两个半径之和，则两个球面的距离=球心距离-两半径之和；否则，两个球面必定有交点，距离赋值为0

之后模版走起

#include <cstdio>  
#include <algorithm>  
#include <iostream>  
#include <cstring>  
#include <cmath>  
#include <cstdlib>  
#include <string>  
#include <map>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <cctype>  
using namespace std;  

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30

const int maxn=200;
const int maxm=10050;
int F[maxn];
double x[maxn];
double y[maxn];
double z[maxn];
double r[maxn];
struct Edge
{
	int u,v;
	double w;
}edge[maxm];

int tol;
void addedge(int u,int v,double w)
{
	edge[tol].u=u;
	edge[tol].v=v;
	edge[tol++].w=w;
}

bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}

int find(int x)
{
	if (F[x]==-1) return x;
	return F[x]=find(F[x]);
}

double Kruskal(int n)
{
	Fill(F,-1);
	sort(edge,edge+tol,cmp);
	int cnt=0;
	double ans=0;
	for(int i=0;i<tol;i++)
	{
		int u=edge[i].u;
		int v=edge[i].v;
		double w=edge[i].w;
		int t1=find(u);
		int t2=find(v);
		if (t1!=t2)
		{
			ans+=w;
			F[t1]=t2;
			cnt++;
		}
		if (cnt==n-1) break;
	}
	// (cnt<n-1) return -1;
	return ans;
}

int main()
{
	//input; 
	int i,n,m,t,j,k;
	double ans;
	while(cin>>n)
	{
		if (n<=0) break;
		ans=tol=0;
		For2(i,1,n)
		{
			scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
			For2(j,1,i-1)
			{
				double dist=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]))-r[i]-r[j];
				if (dist<=0) addedge(i,j,0);
				else addedge(i,j,dist);
			}
		}
		ans=Kruskal(n);
		//cout<<ans<<endl;
		printf("%.3lf\n",ans);
	}
	return 0;
}

D - Constructing Roads

题中给了n*n的矩阵，值是i点到j点的建边的花费，其中已经建好了m条边，题中求还需要花费多少才能使该图连通

思路：Kruskal更好做（并查集）。初始化之后，将m条边依次加入并查集，只要能合并及时合并。

剪枝：一个小的剪枝就是并查集的合并只需要合并n-1次就必然的已经有解，因此用一个全局变量cnt统计次数，及时退出

#include <cstdio>  
#include <algorithm>  
#include <iostream>  
#include <cstring>  
#include <cmath>  
#include <cstdlib>  
#include <string>  
#include <map>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <cctype>  
using namespace std;  

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30

const int maxn=1000;
const int maxm=500000;
int F[maxn];
int cnt;
struct Edge
{
	int u,v,w;
}edge[maxm];


int tol;
int Map[maxn][maxn];

void addedge(int u,int v,int w)
{
	edge[tol].u=u;
	edge[tol].v=v;
	edge[tol++].w=w;
}

bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}

int find(int x)
{
	if (F[x]==-1) return x;
	return F[x]=find(F[x]);
}

int Kruskal(int n)
{
	sort(edge,edge+tol,cmp);
	int ans=0;
	for(int i=0;i<tol;i++)
	{
		int u=edge[i].u;
		int v=edge[i].v;
		int w=edge[i].w;
		int t1=find(u);
		int t2=find(v);
		if (t1!=t2)
		{
			ans+=w;
			F[t1]=t2;
			cnt++;
		}
		if (cnt==n-1) break;
	}
	if (cnt<n-1) return 0;
	return ans;
}

int main()
{
	//input;
	int i,n,m,x,y,z,ans,t,j,k;
	while(cin>>n)
	{
		cnt=ans=tol=0;
		Fill(Map,0);
		Fill(F,-1);
		For2(i,1,n)For2(j,1,n)scanf("%d",&Map[i][j]);
		For2(i,1,n-1)
			For2(j,i+1,n)
			{
				addedge(i,j,Map[i][j]);
				//addedge(j,i,Map[i][j]);
			}
		cin>>m;
		For2(i,1,m)
		{
			scanf("%d%d",&x,&y);
			int u=find(x);
			int v=find(y);
			if (u!=v)
			{
				F[u]=v;
				cnt++;
			}
			//F[x]=y;
		}
		ans=Kruskal(n);
		cout<<ans<<endl;
	}
	return 0;
}

E - QS Network

这个题读题特别费劲，其实还是模版题

建图：给你的n*n矩阵不是直接的花费，而是边花费，总花费=边花费+两个端点的花费。之后模版走起

#include <cstdio>  
#include <algorithm>  
#include <iostream>  
#include <cstring>  
#include <cmath>  
#include <cstdlib>  
#include <string>  
#include <map>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <cctype>  
using namespace std;  

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30

const int maxn=600;
const int maxm=300000;
int F[maxn];
int cost[maxn];
int Cost[maxn][maxn];
struct Edge
{
	int u,v,w;
}edge[maxm];

int tol;
void addedge(int u,int v,int w)
{
	edge[tol].u=u;
	edge[tol].v=v;
	edge[tol++].w=w;
}

bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}

int find(int x)
{
	if (F[x]==-1) return x;
	return F[x]=find(F[x]);
}

int Kruskal(int n)
{
	Fill(F,-1);
	sort(edge,edge+tol,cmp);
	int cnt=0;
	int ans=0;
	for(int i=0;i<tol;i++)
	{
		int u=edge[i].u;
		int v=edge[i].v;
		int w=edge[i].w;
		int t1=find(u);
		int t2=find(v);
		if (t1!=t2)
		{
			ans+=w;
			F[t1]=t2;
			cnt++;
		}
		if (cnt==n-1) break;
	}
	// (cnt<n-1) return -1;
	return ans;
}

int main()
{
	//input; 
	int i,n,m,x,y,z,ans,t,j,k;
	cin>>t;
	while(t--)
	{
		Fill(cost,0);
		Fill(Cost,0);
		ans=tol=0;
		cin>>n;
		For2(i,1,n) scanf("%d",&cost[i]);
		For2(i,1,n)For2(j,1,n) scanf("%d",&Cost[i][j]);
		For2(i,1,n-1)
			For2(j,i+1,n)
			{
				addedge(i,j,cost[i]+cost[j]+Cost[i][j]);
				//addedge(j,i,cost[i]+cost[j]+Cost[i][j]);
			}
		ans=Kruskal(n);
		cout<<ans<<endl;
	}
	return 0;
}


PS：代码的逻辑性都是一样的，之后为了大家的阅读方便（不要揭穿我，其实是我懒），就不贴代码了

F - Truck History

建图：每两个字符串之间的相同位置不同字符的个数为其权值模版走起


G - Arctic Network

Kruskal建图

求最小生成树第K大（小）边的题目。
一般这种题目都是一个原本的连通图分割成s个连通分量，求这些连通分量中最长边。
那么这就是求原图中最小生成树中第s大的边的长度。
因为连接这s个连通分量的边肯定要求是前s-1长的边，这些边有s-1个。

用Kruskal更方便，直接在返回的时候return所求边即可


H - Highways

模版题。但是注意输出时与权值无关，而是在图中需要建立那些边


I - Agri-Net

模版题


J - Borg Maze

这个专题里面仅有的一道综合题：最小生成树+BFS

题意：n*m的矩阵，空格代表可以走，#表示墙，A和S代表其中的点

建图：把图中各个字母之间的BFS的路径值存为边权值，跑最小生成树模版

思路：在输入时，把读入的读全部改掉：字母改为该点的数字编号，依次递增；空格和#改为自己习惯的搜索分隔符

细节：此题用Kruskal更方便，因为在添加边的时候，在图中便已知了起点和终点，权值便是BFS跑出的值

模版走起AC（其中的原理好懂，代码不太好写，祝大家1A）

（就是不给代码，你来打我啊）


K - The Unique MST

次小生成树http://www.cnblogs.com/hxsyl/p/3290832.html

我的理解就是：把属于最小生成树的每一条边都试着从不属于的交换一条边，若仍然满足是生成树则记录其权值，所有可行的情况中权值最小的就是次小生成树

#include <cstdio>  
#include <algorithm>  
#include <iostream>  
#include <cstring>  
#include <cmath>  
#include <cstdlib>  
#include <string>  
#include <map>  
#include <vector>  
#include <set>  
#include <queue>  
#include <stack>  
#include <cctype>  
using namespace std;  

#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30

const int maxn=200;
const int maxm=20000;

bool vis[maxn];
int lowc[maxn];
int pre[maxn];
int Max[maxn][maxn];
bool used[maxn][maxn];
int cost[maxn][maxn];

int Prim(int cost[][maxn],int n)
{
	int ans=0,i,j;
	Fill(vis,0);
	Fill(Max,0);
	Fill(used,0);
	vis[1]=true;
	pre[1]=-1;
	For2(i,2,n)
	{
		lowc[i]=cost[1][i];
		pre[i]=1;
	}
	lowc[1]=0;
	For2(i,2,n)
	{
		int minc=inf;
		int p=-1;
		For2(j,2,n)
			if (!vis[j]&&minc>lowc[j])
			{
				minc=lowc[j];
				p=j;
			}
		if (minc==inf) return -1;
		ans+=minc;
		vis[p]=true;
		used[p][pre[p]]=used[pre[p]][p]=true;
		For2(j,1,n)
		{
			if (vis[j]&&used[p][j]) Max[p][j]=Max[j][p]=cost[j][p];
			else if (vis[j]) Max[j][p]=Max[p][j]=max(Max[j][pre[p]],lowc[p]);
			if (!vis[j]&&lowc[j]>cost[p][j])
			{
				lowc[j]=cost[p][j];
				pre[j]=p;
			}
		}
	}
	return ans;
}

int main()
{
	//input;
	int t;
	int n,m,i,j,x,y,z;
	cin>>t;
	while(t--)
	{
		scanf("%d%d",&n,&m);
		For2(i,1,n)For2(j,1,n)cost[i][j]=inf;
		For2(i,1,n) cost[i][i]=0;
		For2(i,1,m)
		{
			scanf("%d%d%d",&x,&y,&z);cost[x][y]=cost[y][x]=z;
		}
		int ans=Prim(cost,n);
		//if (ans>0) cout<<ans<<endl;
		//else puts("Not Unique!");
		int second=inf,temp=inf;
		For2(i,1,n)
			For2(j,1,n)
				if (!used[i][j]&&cost[i][j]!=0&&cost[i][j]!=inf)
				{
					temp=ans-Max[i][j]+cost[i][j];
					second=min(second,temp);
				}
		if (second==ans) puts("Not Unique!");
		else cout<<ans<<endl;
	}
	return 0;
}
对上面变量的解释：（bin神的模版，大家不要打我）

Max[i][j]表示的是在最小生成树中，点i到点j经过的所有的边中，权值最大的一条

used[i][j]为真，代表它属于最小生成树；否则，不属于

Prim的之后那段代码，本质上就是对Dijkstra中的两点权值的更改与重新记录，各位大神画个图就可以明白啦


L

M

N

都是跟前面非常类似的，看懂了题自己去刷吧，本弱不管了


祝：大家早日AK此专题，还有希望各位大神刷完别的专题也能写份题解让本弱学习学习！

谢谢bin神对本弱的大力支持！

全部评论

相关推荐

11-28 17:56
Momenta_算法
Momenta入职感受
给大家详细聊一聊公司上班细节，大家可以评估下自己来了能否适应。智驾整体强度都比较大，因为基本都算初创公司，还没做到能躺着收钱的地步，凡事看两面，压力大但是能学到东西，不至于说每天干重复的东西么没有提示，工作时间10am-19pm，项目交付的时候加班就多，基本上9点左右，公司包三餐&nbsp;工作再忙都要好好吃饭&nbsp;公司统一使用美餐app&nbsp;可以根据自己喜好来订餐到工位餐区也可以去楼下美好荟去合作商家堂食比如：老乡鸡&nbsp;costa&nbsp;美餐20元餐标超出部分自己补差价👇&nbsp;王阿吉的快餐真的很好吃强推&nbsp;）别担心会吃腻&nbsp;行政小姐姐会定期更换合作商家。其他福利&nbsp;，中秋节有公司定制周边和礼盒（全年就中秋有），出行方面内部员...
Momenta公司福利 297人发布
点赞 评论 收藏
分享
11-30 20:19
门头沟学院 C++
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
10-31 17:15
已编辑
点赞 评论 收藏
分享
10-11 16:54
河北工程技术学院 测试工程师
这样的简历，HR会看？
offer多多的六边形战士很无语：看了你的博客，感觉挺不错的，可以把你的访问量和粉丝数在简历里提一下，闪光点（仅个人意见）
点赞 评论 收藏
分享
11-26 09:40
莆田学院 产品经理
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 25届秋招总结 #
451087次浏览 4613人参与
# 如何排解工作中的焦虑 #
72336次浏览 1008人参与
# 地方国企笔面经互助 #
8311次浏览 18人参与
# 同bg的你秋招战况如何？ #
82258次浏览 602人参与
# 找工作时遇到的神仙HR #
565371次浏览 3851人参与
# 实习，投递多份简历没人回复怎么办 #
2458790次浏览 34885人参与
# 虾皮求职进展汇总 #
122189次浏览 913人参与
# 比亚迪工作体验 #
45080次浏览 214人参与
# 春招别灰心，我们一人来一句鼓励 #
44520次浏览 553人参与
# 现在还是0offer，延毕还是备考 #
826414次浏览 6924人参与
# 你最近一次加班是什么时候？ #
22267次浏览 203人参与
# 提前批简历挂麻了怎么办 #
150373次浏览 1980人参与
# 校招入职后的感受 #
162847次浏览 1988人参与
# 如果公司给你放一天假，你会怎么度过？ #
4899次浏览 63人参与
# 百度秋招提前批进度 #
87868次浏览 1043人参与
# 发工资后，你做的第一件事是什么 #
13612次浏览 63人参与
# 实习必须要去大厂吗？ #
56154次浏览 965人参与
# 双非本科求职如何逆袭 #
663977次浏览 7413人参与
# 晒一晒我的offer #
10009448次浏览 106266人参与
# 查收我的offer竞争力报告 #
37918次浏览 424人参与
牛客网
牛客企业服务