最小生成树（Kruskal算法及相关例题）

1.Kruskal算法概念以及基本思路

（1）概念：

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。它的时间复杂度为O（ElogE）(E是图G的边的总数)，适合于求边稀疏的网的最小生成树。

其基本思想是：假设连通网G，令最小生成树的初始状态为只有n个顶点且没有任何一条边的图T，概述图中每个顶点自成一个连通分量。在E中选择代价最小（即距离最短）的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。换而言之就是在整个图找最短的边，从短到长一次寻找，若没有连通，则进行连通，若已经连通，则放弃这个边，去寻找下一个，知道变成连通图

（2）基本思路：

从它的基本思想我们可以得出做题时的基本思路：

1.首先创建一个一维数组，用于判断这个点是否连通，每个数组的初始值都对应自己的下标

2.创建一个结构体，存储位置信息，以及之间的长度

3.通过快排进行排序，将路径最短的排在前面

4.根据题解去寻找最小生成树

2.相关例题

第一题：最小生成树

题解：这题就是最基本的最小生成树问题，没有什么难度

#include<bits/stdc++.h>
using namespace std;

int n,m;//n个结点和m条边
struct lu//代表路径的结构体
{
	int start;//起始节点
	int end1;//终止结点
	int l;//路径长度
}q[200005];
int f[50005];//用于判断是否连通的数组
int count1;//统计已经连通几条边
long long sum;//总长度

int cha(int x)//查，判断是否属于同一个根节点
{
	if(f[x]==x)
	return x;
	return cha(f[x]);
}

void bing(int root1,int root2)//并，将根节点并在一起
{
	if(root1==root2)
	return;
	f[root2]=root1;
}

bool cmp(lu a,lu b)//路径要根据路径长度进行比较
{
	return a.l<b.l;//快排顺序，从小到大排列路径长度
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		f[i]=i;//将根节点设置为自己
	}
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&q[i].start,&q[i].end1,&q[i].l);
	}
	sort(q+1,q+m+1,cmp);//快排
	for(int i=0;i<m;i++)
	{
		if(cha(q[i].start)==cha(q[i].end1))//如果已经并在一起就直接跳过
		continue;
		bing(cha(q[i].start),cha(q[i].end1));
		sum+=q[i].l;
		count1++;
		if(count1==n-1)//当满足了连通图，这个是连通图的性质，边数=顶点数-1
		break;
	}
	if(count1<n-1)//如果是非连通图
	{
		printf("orz");
		return 0;
	}
	printf("%d",sum);
	return 0;
}

第二题：拆地毯

题解：这题其实就是最小生成树的地方略变一点儿，求的是最大生成树，我们要找的是最长的长度，那么我们只需要改变一下快排的方式即可

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct lu
{
	int start;
	int end1;
	int l;
}q[100005];
int f[100005];
int count1;
int sum;
int cha(int x)
{
	if(f[x]==x)
	return x;
	return cha(f[x]);
}
void bing(int root1,int root2)
{
	if(root1==root2)
	return ;
	f[root2]=root1;
}
bool cmp(lu a,lu b)
{
	return a.l>b.l;//改变一下快排的方式
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&q[i].start,&q[i].end1,&q[i].l);
		
	}
	sort(q,q+m,cmp);
	for(int i=0;i<m;i++)
	{
		if(cha(q[i].start)==cha(q[i].end1))
		continue;
		bing(cha(q[i].start),cha(q[i].end1));
		count1++;
		sum+=q[i].l;
		if(count1==k)//当保留的地毯满足保留的个数结束就可以
		break;
	}
	printf("%d",sum);
	return 0;
}

第三题：无线通讯网

题解：也是最小生成树类的题目，但是没什么的，唯一改变的地方就是因为这个地方不是求路径和，而是卡的最小的无线电所需要的距离，也就是卡的极限最小值

#include<bits/stdc++.h>
using namespace std;
int s,p;
int x[505],y[505];
int f[1000005];
struct lu
{
	int start;
	int end1;
	double l;
}q[2000005];
int count1;
double sum;
int cha(int x)
{
	if(f[x]==x)
	return x;
	return cha(f[x]);
}
void bing(int root1,int root2)
{
    if(root1==root2)
	return ;
	f[root2]=root1;	
}
bool cmp(lu a,lu b)
{
	return a.l<b.l;
}
int main()
{
	int flag=0;
	scanf("%d%d",&s,&p);
	for(int i=1;i<=p;i++)
	f[i]=i;
	for(int i=1;i<=p;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		for(int j=1;j<i;j++)
		{
			flag++;
			q[flag].start=i;
			q[flag].end1=j;
			q[flag].l=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
	}
	sort(q+1,q+1+flag,cmp);
	for(int i=1;i<=flag;i++)
	{
		if(cha(q[i].start)==cha(q[i].end1))
		continue;
		sum=q[i].l;//长度就是那个极限的值
		bing(cha(q[i].start),cha(q[i].end1));
		count1++;
		if(count1==p-s)//当满足了结束条件
		break;
	}
	printf("%.2lf",sum);
	return 0;
}

第四题：营救

题解：也是最小生成树的题目和第三题其实一样，只不过排的是拥挤度

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t;
struct lu
{
	int start;
	int end1;
	int l;
}q[20005];
int f[10005];
int count1;
int sum;
int cha(int x)
{
	if(f[x]==x)
	return x;
	return cha(f[x]);
}
void bing(int root1,int root2)
{
	if(root1==root2)
	return ;
	f[root2]=root1;
}
bool cmp(lu a,lu b)
{
	return a.l<b.l;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&q[i].start,&q[i].end1,&q[i].l);
	}
	sort(q,q+m,cmp);
	for(int i=0;i<m;i++)
	{
		bing(cha(q[i].start),cha(q[i].end1));
		sum=q[i].l;
		if(cha(s)==cha(t))
		{
			break;
		}
	}
	printf("%d",sum);
	return 0;
}

第五题：买礼物

题解：这题有一个坑，就是有可能绑定在一起买比单个买还要贵，因此我们在进行价值的计算时需要有一个判断

#include<bits/stdc++.h>
using namespace std;
int a,b;
struct wu
{
	int x,y;
	int w;
}q[250005];
int f[505];
int sum;
int count1;
int cha(int x)
{
	if(f[x]==x)
	return x;
	return cha(f[x]);
}
void bing(int root1,int root2)
{
	if(root1==root2)
	{
		return ;
	}
	f[root2]=root1;
}
bool cmp(wu a,wu b)
{
	return a.w<b.w;
}
int main()
{
	scanf("%d%d",&a,&b);
	sum=a;
	for(int i=1;i<=b;i++)
	f[i]=i;
	for(int i=1;i<=b;i++)
	{
		for(int j=1;j<=b;j++)
		{
			count1++;
			scanf("%d",&q[count1].w);
			q[count1].x=i;
			q[count1].y=j;
			if(q[count1].w==0)
			q[count1].w=a;
		}
	}
	sort(q+1,q+1+count1,cmp);
	for(int i=1;i<=count1;i++)
	{
		if(cha(q[i].x)==cha(q[i].y))
		continue;
		bing(cha(q[i].x),cha(q[i].y));
		sum+=min(q[i].w,a);//去优惠价格和原价格的小值
	}
	printf("%d",sum);
	return 0;
}