考研复试系列——第六节 最小生成树

前言

基础知识

//Kruskal算法基本原理：/**	1. 初始时所有节点都属于孤立的集合*	2. 按照边的权重的递增顺序遍历，若遍历到的边的两个节点分别属于不同的集合，*	   则确定改边为最小生成树上的一条边，并将这两个节点分属的集合合并	*   3. 遍历结束后，所有节点属于同一个集合，则被选取的边和原图所有节点构成最小生成树*	   否则原图不连通，最小生成树不存在*///Prim算法基本原理：/**	1. 初始时所有节点都属于孤立状态*	2. 选择图中任意一节点为起始点，并将其加入集合V，找到另一个节点满足到集合V的任一节点的*	   权重最小，将该节点加入集合V，该节点到集合V中的那一节点的路径即为MST的一条边。*	3. 当所有节点全部加入集合V时结束**/
例题
例题一
第一行输入N，表示有N个城市（ N< 100），接下来输入 N * （N-1）/2 行对应两个城市的标记以及城市之间的距离，现在这些城市之间修路，是各城市能够联通，求最小的公路长度。sample input ：31 2 11 3 22 3 44 1 2 11 3 41 4 12 3 32 4 23 4 50sample output：35思考：首先很明显确定这是一道求MST的问题，我们先使用Kruskal算法来解决它
#include<iostream>#include<algorithm>using namespace std;int city[101];//最多有100个城市int length;//记录结果struct Edge{	int a;	int b;	int weight;}edges[6000];int Find(int x)//关于集合的操作我们仍利用并查集{	int r = x;	while(r != city[r])		r = city[r];	int i=x,j;	while(city[i] != r)//路径压缩	{		j = city[i];		city[i] = r;		i = j;	}	return r;}void Join(int x,int y,int i){	int fx = Find(x),fy = Find(y);	if(fx != fy)	{		city[fy] = fx;		length += edges[i].weight;	}}bool cmp(Edge A,Edge B){	return A.weight < B.weight;}int main(){	int n;//城市个数	int i;	while(cin>>n && n)	{		length = 0;		for(i=1;i<=n;i++)//所有节点处于独立状态			city[i] = i;				int count = n * (n-1) / 2;		for(i=1;i<=count;i++)//输入信息			cin>>edges[i].a>>edges[i].b>>edges[i].weight;		sort(edges+1,edges+1+count,cmp);		for(i=1;i<=count;i++)			Join(edges[i].a,edges[i].b,i);		cout<<length<<endl;	}	return 0;}有了并查集的基础，再来做这道题目是非常简单的，我们只是在并查集的基础上进行了输入序列的排序工作，其它与上一节讲的并查集的知识是完全相同的。
例题二
在平面上有一些点，我们使用一些线段将这些点链接起来，要求所有线段的长度和最小，求出该长度。sample input ：31.0 1.02.0 2.02.0 4.0sample output：3.41思考 ：这道题目其实和上一道原理一样，依然是求最小生成树，只不过是输入的数据发生了变化，这里是点的坐标而不是点与点之间的距离，我们要做的只是确定点与点之间的距离作为算法的输入数据，其它处理方式和上一题是一样的。
#include<iostream>#include<algorithm>#include<iomanip>#include<math.h>using namespace std;int nodes[101];double length;struct Edge{	int a,b;	double weight;	bool Operator < (const Edge &A) const	{		return weight < A.weight;	}}edges[6000];struct Point{	double x,y;}points[101];	double getDistance(Point a,Point b){	double tmp =  (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);	return sqrt(tmp);}int Find(int x){	int r = x;	while( r != nodes[r])		r = nodes[r];	int i=x,j;	while(nodes[i] != r)	{		j = nodes[i];		nodes[i] = r;		i = j;	}	return r;}void Join(int x,int y,int i){	int fx = Find(x),fy = Find(y);	if( fx != fy )	{		nodes[fy] = fx;		length += edges[i].weight;	}}int main(){	int n;	while(cin>>n && n)	{		length = 0.0f;		int i,j;		for(i=1;i<=n;i++)			cin>>points[i].x>>points[i].y;		int edge_index = 1;		for(i=1;i<=n;i++)		{			for(j=i+1;j<=n;j++)			{				edges[edge_index].a = i;				edges[edge_index].b = j;				edges[edge_index].weight = getDistance(points[i],points[j]);				edge_index++;			}		}		sort(edges+1,edges+1+edge_index);						for(i=1;i<=n;i++)			nodes[i] = i;		for(i=1;i<edge_index;i++)		{			Join(edges[i].a,edges[i].b,i);		}		cout<<finxed<<setprecision(2)<<length<<endl;//结果保留两位小数	}	return 0;}
例题三
给出n个球体的球心坐标和半径，可以在两个球体的表面连一条通路，代价为距离，求使得所有球体联通的最小花费。注意：两点之间的距离为 球心距 - 半径和，若这个式子小于0 则距离为0 。 （所有值都不超过100）输入为球心坐标x , y , z 然后为半径r sample input：310.000 10.000 50.000 10.00040.000 10.000 50.000 10.00040.000 40.000 50.000 10.000230.000 30.000 30.000 20.00040.000 40.000 40.000 20.00055.729 15.143 3.996 25.8376.013 14.372 4.818 10.67180.115 63.292 84.477 15.12064.095 80.924 70.029 14.88139.472 85.116 71.369 5.5530sample output：20.0000.00073.834
#include<iostream>#include<math.h>#include<algorithm>#include<iomanip>using namespace std;int ball[101];double ans;struct Ball{	double x,y,z;//球心坐标	double r;//半径}balls[101];struct Edge{	int a,b;	double weight;	bool operator < (const Edge& A) const	{		return weight < A.weight;	}}edges[6000];double getDistance(Ball A,Ball B)//计算两球之间的距离{	double tmp = (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) + (A.z - B.z) * (A.z - B.z);	return sqrt(tmp) - A.r - B.r;}int Find(int x)//依旧使用并查集{	int r = x;	while(r != ball[r])		r = ball[r];	int i = x,j;	while(ball[i] != r)	{		j = ball[i];		ball[i] = r;		i = j;	}	return r;}void Join(int x,int y,int i){	int fx = Find(x),fy = Find(y);	if(fx != fy)	{		ball[fy] = fx;		if(edges[i].weight > 0 )			ans += edges[i].weight;	}}int main(){	int n;//球的个数	int i;	while(cin>>n && n)	{		ans = 0.0f;		for(i=1;i<=n;i++)		{			cin>>balls[i].x>>balls[i].y>>balls[i].z>>balls[i].r;			ball[i] = i;		}		int j;		int edgeCount = 1;		for(i=1;i<=n;i++)		{			for(j=i+1;j<=n;j++)			{				edges[edgeCount].a = i;				edges[edgeCount].b = j;				edges[edgeCount].weight = getDistance(balls[i],balls[j]);				edgeCount++;			}		}		sort(edges+1,edges+1+edgeCount);		for(i=1;i<edgeCount;i++)			Join(edges[i].a,edges[i].b,i);		cout<<fixed<<setprecision(3)<<ans<<endl;//结果保留三位小数	}		return 0;}满满的套路，只需要掌握一套模板，就可以解决很多相关的问题了，不过关键是要理解，方能以不变应万变。
例题4 
有N个村庄，标记为1至N，进行修路使这些村庄互通有无，输入：第一行输入N （3<= N <= 100）意味着村庄的数量，接下来输入三行数据第 i 行有N个数，对于第 i 行第 j 个数表示村庄 i 和村庄 j 的距离 （该距离为整数，且区间为 【 1 ，1000】）。然后又有一行，有一个整数Q，（0<= Q <= N * (N - 1) /2 )。接下来有 Q行 ，每行有两个数a 和 b 表示村庄 a 和 b的路已经修好了。输出结果为实际的总长度（含已修好的路径长度）sample input：30 990 692990 0 179692 179 011 2sample output：1169思考：首先确定这道题目也是一道MST的题目，只是稍有不同，因为有些路径是我们一定要选择的，如何处理这些路径是解题的关键。考虑这样一种策略，我们先假设这些已经修好的路径的长度为0，然后按照原先的算法处理，发现这样可以保证这些边一定被选择，但是最终的路径长度的结果肯定少算了，没关系我们加上即可。如此就可以解决这道问题了。进一步将，我们在实际实现时，进行sort对边排序时，如果把这些已经finish的边放最前面不就轻而易举的解决问题了吗。
#include<iostream>#include<algorithm>using namespace std;int pre[101];int ans;struct Edge{	int a,b;	int weight;	bool isFinish;	bool operator < (const Edge& A) const	{		if(A.isFinish)//如果已经完成则排序放前面			return false;		return weight < A.weight;	}}edges[6000];int Find(int x){	int r = x;	while(r != pre[r])		r = pre[r];	int i = x,j;	while(pre[i] != r)	{		j = pre[i];		pre[i] = r;		i =j;	}	return r;}void Join(int x,int y,int i){	int fx = Find(x),fy = Find(y);	if(fx != fy)	{		pre[fy] = fx;		ans += edges[i].weight;	}}void ChangeTag(int a,int b,int k)//修改标记isFinish{	if(b < a) //保证 b > a	{		int temp = b;		b = a;		a = temp;	}	int i;	for(i=1;i<=k;i++)	{		if(edges[i].a == a && edges[i].b == b)			edges[i].isFinish = true;	}}int main(){	int n,i,j,k;	while(cin>>n && n)	{		k = ans = 0;		int distance;		for(i=1;i<=n;i++)		{			for(j=1;j<=n;j++)			{				cin>>distance;				if(j > i) //排除冗余的距离信息，因为输入关于对角线对称				{					k++;//若n=3，最后k=3					edges[k].a = i;					edges[k].b = j;					edges[k].weight = distance;					edges[k].isFinish = false;				}			}		}		for(i=1;i<=n;i++)			pre[i] = i;		int q,a,b;		cin>>q;		for(i=1;i<=q;i++)		{			cin>>a>>b;			ChangeTag(a,b,k);		}		sort(edges+1,edges+k+1);		for(i=1;i<=k;i++)		{			Join(edges[i].a,edges[i].b,i);		}		cout<<ans<<endl;	}	return 0;}这道题目是POJ上的一道题目的变形，原题是求除了已经修好的路程，还需要的最少的路径长度。其实原题更加简单，对于已经修好的路程我们使其权值weight为0然后正常计算即可，而且此时不用使用isFinish标记，其余是与例题一相似的。