Time Limit: 1000MS
Memory Limit: 65536KB
Problem Description
有n个城市，其中有些城市之间可以修建公路，修建不同的公路费用是不同的。现在我们想知道，最少花多少钱修公路可以将所有的城市连在一起，使在任意一城市出发，可以到达其他任意的城市。
Input
输入包含多组数据，格式如下。
第一行包括两个整数n m，代表城市个数和可以修建的公路个数。(n <= 100， m <=10000)
剩下m行每行3个正整数a b c，代表城市a 和城市b之间可以修建一条公路，代价为c。
Output
每组输出占一行，仅输出最小花费。
Example Input
3 2
1 2 1
1 3 1
1 0
Example Output
2
0
Hint
Author
http://blog.csdn.net/yeruby/article/details/38615045
MST（Minimum Spanning Tree，最小生成树）问题有两种通用的解法，Prim算法就是其中之一，它是从
点的方面
考虑构建一颗MST，大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点(刚刚新加入的点)c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以该MST就有N-1条边，每一次向集合V中加入一个点，就意味着找到一条MST的边。
kruskal：基于并查集的贪心算法（http://blog.csdn.net/luomingjun12315/article/details/47700237）
并查集：http://blog.csdn.net/dellaserss/article/details/7724401
//Prime算法
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f;
int Map[110][110],vn[110],lowcost[110],n,m,sum,flag;
//vn用于存储第一个随机选取的结点以及之后新加入的,共需要存储n个
//Map初始设为inf,当边长小于inf时才将Map更新
//lowcost存储从k到i（i>=1&&i<=n）的边长,并找到最小的
//当lowcost中找不到小于inf的边时利用flag终止循环,说明无法构成最小生成树
void Prim()
{
int k,t;//k、t：及时更新当前要找最小边的结点
vn[1]=1;
for(int i=2; i<=n; i++)
{
lowcost[i]=Map[1][i];
}
k=1;
for(int i=2; i<=n; i++)
{
int temp=inf;
for(int i=2; i<=n; i++)
{
if(lowcost[i]<temp&&!vn[i])
{
temp=lowcost[i];
t=i;
}
}
if(temp==inf)
{
flag=1;
break;
}
sum+=temp;
k=t;
vn[k]=1;
for(int j=2; j<=n; j++)
{
if(lowcost[j]>Map[k][j]&&!vn[j])
{
lowcost[j]=Map[k][j];
}
}
}
}
int main()
{
while(cin>>n>>m)
{
int x,y,z;
flag=0;
memset(Map,inf,sizeof(Map));
memset(vn,0,sizeof(vn));
sum=0;
for(int i=0; i<m; i++)
{
cin>>x>>y>>z;
if(Map[x][y]>z)
{
Map[x][y]=Map[y][x]=z;
}
}
Prim();
if(!flag)
cout<<sum<<endl;
else
cout<<-1<<endl;
}
return 0;
}
//Kruskal算法
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
int b,e,w;
};
bool cmp(node x,node y) //比较函数，按权值升序排列
{
return x.w<y.w;
}
int Find(int pre[],int k) //查找连通分量顶点
{
while(k!=pre[k])//防止连通分量顶点变化后返回的仍是原先未变化的连通分量值
k=pre[k];
return k;
}
void Kruskal(node g[],int m,int n)
{
int i,sum=0,cnt=0;
int pre[100];
for( i=1; i<=n; i++)
pre[i]=i;
for( i=0; i<m; i++)
{
int x=Find(pre,g[i].b);
int y=Find(pre,g[i].e);
if(x!=y) //不相等，说明不在一个连通分量，不构成回路
{
pre[x]=y; //将y加入x的连通分量
sum+=g[i].w; //计算路径
}
}
cout <<sum<<endl;
}
int main()
{
int n,m;
node g[10000];
while(cin>>n>>m)
{
for(int i=0; i<m; i++) //建立边集数组
{
int a,b,d;
cin>>a>>b>>d;
g[i].b=a;
g[i].e=b;
g[i].w=d;
}
sort(g,g+m,cmp);
Kruskal(g,m,n);
}
return 0;
}
