欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-11 11:49:38
此题数组大小非常重要 算法过程: 现将全部边按照权值(由小到大)排序。 按顺序(同上)考虑每条边,只要这条边和之前已选择的边不构成圈,就保留这条边,否则放弃这条边。 具体算法 成功选择(n-1)条边后,形成一颗最小生成树,如果无法选择出(n-1)条边,则说明不连通。 当所有的点都连到一起时,执行结束 ......

此题数组大小非常重要

算法过程:

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

具体算法

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

为何是n-1条边呢?

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

上图形式可转化为下图形式【图*有n个圆,共有(n-1)条边】

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

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

是不是非常简单易懂?

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

在此附上详细代码

#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; }

时间复杂度:O(NlogN)【N是结点个数】

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