题目描述
有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。输入
输入包含多组数据，格式如下。第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。输出
每组输出占一行，仅输出最小花费。示例输入
3 2
1 2 1
1 3 1
1 0
示例输出
2
0
提示
#include <stdio.h>
#include <stdlib.h>
struct node
{
int u,v,w;
};
int h[150],sum;
int find(int k)
{
int r=k;
while(h[r]!=r)
r=h[r];
int i=r,j;
while(i!=r)
{
j=h[i];
h[i]=r;
i=j;
}
return r;
}
void merge(int x,int y,int z)
{
int tx=find(x),ty=find(y);
if(tx!=ty)//不能联通根不一样必须连起来
{
sum=sum+z;
h[tx]=ty;
}
}
int main()
{
int n,m,i,j;
struct node mp[10010],t;
while(~scanf("%d%d",&n,&m))
{ sum=0;
for(i=1;i<=n;i++)
h[i]=i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&mp[i].u,&mp[i].v,&mp[i].w);
}
for(i=1;i<=m-1;i++)
{
for(j=i+1;j<=m;j++)
{
if(mp[i].w>mp[j].w)
{
t=mp[i];
mp[i]=mp[j];
mp[j]=t;
}
}
}
for(i=1;i<=m;i++)
{
merge(mp[i].u,mp[i].v,mp[i].w);
}
printf("%d\n",sum);
}
return 0;
}
//跟并查集差不多,先排序再并查集做，从小到大不连通则连起来