RT，题目链接http://zju.acmclub.com/index.php?app=problem_title&id=1&problem_id=2336
需要注意的问题有：
1.可以使用Kruskal算法，在判断回路时使用并查集结构；
2.并查集使用树的双亲指针数组作为存储结构，大小为树中点的数目；
初始化时：初始每一个点为一个单独的联通分量，S[i]=-1 for 1<=i<=|V|；
Find(S,x)：返回单元素x所在的子集合名字（用树根来代表），这里如果两个点所返回的子集合名字相同，说明这两个点同属于一个连通分量；这种情况也说明，如果把当前边再加入这个连通分量中，就会产生回路；
Union(S,root1,root2)：把以x为根的子集合与以y为根的子集合合并到一起；即对应把两个连通分量合并为一个，root1和root2可以通过Find函数找到根；
3.需要额外判断给定的数据是否能使图连通，方法是执行Kruskal算法后，数一数S[]数组中-1的个数，它的个数cnt即代表了算法结束后连通分量的个数，如果为1，说明有一个MST；否则若图不连通，树也必定不连通，故cnt一定大于1
4.边集用结构体数组来存，可以开的大一点，我刚开始就是开小了返回段错误；
5.排序可以用高效的库函数qsort，自己写一个比较函数MyCmp实现结构体数组按特定值排序的功能，刚开始我是自己用的起泡排序+用邻接矩阵来存树，结果果断时间超限。。。
cpp代码：
#include<iostream>
#include<cstdlib>
#define VERTEX_MAX 101
#define EDGE_MAX 5000
using namespace std;
//并查集类，根据并查集就可以判断图是否是连通的
class UFSets
{
private:
int S[VERTEX_MAX];
public:
UFSets(int size_vertex){
for (int i=1;i<=size_vertex;i++)S[i]=-1;
}
~UFSets(){}//析构
void print(int size_vertex){//输出当前并查集数组测试一下
for (int i=1;i<=size_vertex;i++)cout<<S[i]<<" ";
cout<<endl;
}
int Find(int x){//在S中查找包含x的树的根
while(S[x]>=0)x=S[x];
return x;
}
void Union(int root1,int root2){
S[root2]=root1;
}
int isConnect(int size_vertex){
int cnt=0;//记录数组中-1的个数，有几个-1说明有几个连通分量
for (int i=1;i<=size_vertex;i++){
if (S[i]==-1)cnt++;
}
if (cnt==1)return 1;
else return 0;
}
};
struct EDGES{
int x;
int y;
int w;
};
int MyCmp(const void*a,const void*b)
{
return (*(EDGES*)a).w-(*(EDGES*)b).w;
}
int main(){
int n,m,a,b,l,k,pos;
int mk[VERTEX_MAX];
struct EDGES edge[EDGE_MAX];
while(cin>>n>>m){
if (n==0)break;
pos=0;
while(n--){
cin>>a>>b>>l;
edge[pos].x=a;
edge[pos].y=b;
edge[pos].w=l;
pos++;
}
qsort(edge,pos,sizeof(edge[0]),MyCmp);
int cost=0;//累积最小生成树的代价
UFSets sets(m);//初始化并查集
//开始生成MST
for(k=0;k<pos;k++){
//每次取权重最小的边
if(sets.Find(edge[k].x)!=sets.Find(edge[k].y)){//如果不构成回路，就增加边
//cout<<"i="<<edge[k].x<<" j="<<edge[k].y<<" w="<<edge[k].w<<endl;
cost+=edge[k].w;
sets.Union(sets.Find(edge[k].x),sets.Find(edge[k].y));
}
}
if(sets.isConnect(m))cout<<cost<<endl;
else cout<<"Error!"<<endl;
}
}