Kruskal算法计算最小生成树，只与边有关，时间复杂度O(eloge)
步骤：
1.将边按权值递增排序
2.依次取出边加入最小生成树中并保证无环，判断是否成环可利用并查集。
例：http://ac.jobdu.com/problem.php?pid=1024
题目描述：
省*“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。
经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct Edge
{int a,b,cost;}edge[200];
int cmp(const Edge &A,const Edge &B)
{
return A.cost<B.cost;
}
int Tree[200];
int findRoot(int x)
{
if(Tree[x]==-1)return x;
else
{
int tmp=findRoot(Tree[x]);
Tree[x]=tmp;
return tmp;
}
}
int judge(int Tree[],int m)
{
int cnt=0;
for(int i=1;i<=m;i++)
{
if(Tree[i]==-1)cnt++;
}
if(cnt!=1)return false;
else return true;
}
int main()
{
int m,n;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0)break;
for(int i=1;i<=m;i++)
{
Tree[i]=-1;
}
int a,b;
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);
}
sort(edge,edge+n,cmp);
int sum=0;
for(int i=0;i<n;i++)
{
int a=findRoot(edge[i].a);
int b=findRoot(edge[i].b);
if(a!=b)
{
Tree[a]=b;
sum+=edge[i].cost;
}
}
if(judge(Tree,m))
{
printf("%d\n",sum);
}
else
printf("?\n");
}
}
版权声明：本文为博主原创文章，未经博主允许不得转载。