首页 > > 程序设计 > C/C++ >

P3366 最小生成树【模板+Kruscal讲解】

2018-07-17 03:56:25来源：博客园阅读 ()

此题数组大小非常重要

算法过程：

现将全部边按照权值（由小到大）排序。
按顺序（同上）考虑每条边，只要这条边和之前已选择的边不构成圈，就保留这条边，否则放弃这条边。

具体算法

成功选择（n-1）条边后，形成一颗最小生成树，如果无法选择出（n-1）条边，则说明不连通。
当所有的点都连到一起时，执行结束。

为何是n-1条边呢？

上图形式可转化为下图形式【图中共有n个圆，共有（n-1）条边】

变！

是不是非常简单易懂?

在此附上详细代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int parent[10000110];
int n,m;
int i,j;
struct edge
{
int u,v,w; //边的顶点，权值
}edges[10000110];
//初始化并查集
void UFset()
{
for(i=1;i<=n;i++) 
parent[i] = -1;
}
//查找i的根 
int find(int i)
{
int temp;
//查找位置
for(temp=i;parent[temp]>=0;temp=parent[temp]);
//压缩路径
while(temp!=i){
int t=parent[i];
parent[i]=temp;
i=t;
}
return temp;
}
//合并两个元素a,b
void merge(int a,int b){
int r1=find(a);
int r2=find(b);
int tmp=parent[r1] + parent[r2]; //两个集合结点数的和
if(parent[r1]>parent[r2])//秩排序 优化 
{
parent[r1]=r2;
parent[r2]=tmp;
}else{
parent[r2]=r1;
parent[r1]=tmp;
}
}
void kruskal()
{
int sumWeight=0;
int num=0;
int u,v;
UFset();
for(int i=0;i<m;i++)
{
u=edges[i].u; 
v=edges[i].v;
    //一个结点一个结点算
if(find(u)!=find(v))
{ //u和v不在一个集合（能够围成一个圈，即在同一个集合中）
sumWeight+=edges[i].w;//计算权值总和 
num++;//计算次数，根据需要添加，可不加 
merge(u,v); //把这两个边加入一个集合。
}
}
printf("%d \n",sumWeight);
}
//排序
int cmp(const void * a, const void * b){
edge * e1 = (edge *)a;
edge * e2 = (edge *)b;
return e1->w - e2->w;
}
int main() {
scanf("%d %d", &n,&m);
for(i=0; i<m; i++)
{
scanf("%d %d %d", &edges[i].u,&edges[i].v,&edges[i].w);
}
qsort(edges,m,sizeof(edge),cmp);//按权值排序 
kruskal();//
return 0;
}