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中的两点权值的更改与重新记录，各位大神画个图就可以明白啦

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

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

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

本文链接：https://blog.csdn.net/kevin66654/article/details/43269709

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

小白通过Fiddler爬取手机app的数据并提取出来（详细版）_王者营地抓包-程序员宅基地

我们就以爬取安卓端上的王者营地上英雄热度榜为例：前期准备工作：下载安装Fiddler，并配置好相关连接选项1.下载：https://www.telerik.com/fiddler，进入网站点击Download now再填写好相关信息，点击红色的Download for Windows，即可完成下载。2.安装基本是往下点就行，确定好安装路径即可。这里，我是选择在我的E盘3.配..._王者营地抓包

node 开发中常用的async/await 处理回调的几种形式_node http内用await-程序员宅基地

一、单一的回调处理//下面两种形式的async函数效果相同，await只能用在async函数内部async function(){}async () => {}（1）http请求var http = require('http');(async () => { var res = await new Promise(function (resolve, reject) { v_node http内用await

《计算机组网试验-配置动态 NAT 》杭州电子科技大学-程序员宅基地

实验过程及步骤（可另附页，使用网络拓扑图等辅助说明）：步骤 1 在路由器上配置 IP 路由选择和 IP 地址。操作过程与结果如下：注：此处已通过图形界面启用SG的FastEthernet 1/0口和 serial1/2口，ISP相应接口也需要开启，也可使用命令noshutdown启用。步骤2 定义一个 IP 访问列表。步骤3 配置静态 NAT。操作过程与结果如下：注：这里发现prefix-length 24在虚拟软件中无法运行，需要使用ne...

Maven项目打jar包报错：Perhaps you are running on a JRE rather than a JDK?_maven打包提示当前环境是jre-程序员宅基地

Maven项目在打jar包时，报错提示：[ERROR] No compiler is provided in this environment. Perhaps you are running on a JRE rather than a JDK?报错的提示已经讲得很清楚，当前运行的环境为JRE，而不是JDK，没有提供编译环境。所以解决的问题关键是将当前项目的运行环境由JRE切换为JDK即可。..._maven打包提示当前环境是jre

关于集合和字符串的互转_字符串集合转字符串-程序员宅基地

关于集合和字符串的互转一个集合转换成字符串，发现import org.apache.commons.lang.StringUtils;有这么一个简单的方法：Stringstr=StringUtils.join(list,",");第一个参数list表示要转换的集合对象，第二个参数“，”表示要把集合用逗号进行隔开，这样一来就省去很多中间转换的步骤，可以直接得到一个用逗号分开的字符串：集合：[篮球, ..._字符串集合转字符串

Spark之广播变量-程序员宅基地

Spark之广播变量广播变量：分布式共享只读变量。广播变量用来高效分发较大的对象。向所有工作节点发送一个较大的只读值，以供一个或多个Spark操作使用。比如，如果你的应用需要向所有节点发送一个较大的只读查询表，广播变量用起来都很顺手。在多个并行操作中使用同一个变量，但是 Spark会为每个任务分别发送。1）使用广播变量步骤：（1）调用SparkContext.broadcast（广播变量）创建出一个广播对象，任何可序列化的类型都可以这么实现。（2）通过广播变量.value，访问该对象的值。（

随便推点

HDU3062-程序员宅基地

有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？Inputn：表示有n对夫妻被邀请 (n<= 1000)m：表示有m 对矛盾关系 ( m < (n - 1) * (n -1))在接下来的m行中，每行会有4个数...

003-Webbuilder应用HTML表单_webbuilder textarea_天又热了的博客-程序员宅基地

HTML和控件的混合编程通常普通的表单界面使用UI控件来构建，对于复杂的界面也可以使用HTML来直接构建，WebBuilder中提供特定的语法可以把相关的控件比如日期控件插入到指定的DOM位置。HTML和控件的混合编程一方面可以使界面的构建更加灵活，另一方面可以充分利用组件库件的强大功能，使两者有机结合起来。显示html所有的UI控件都具有html属性，设置该属性即可在该控件中显示HTML.比如设置panel的html属性可以在panel中显示任意的HTML把控件插入到HTML中通过以下4种方法可_webbuilder textarea