hdu:继续畅通工程（kruskal的MST并查集实现）

Problem Description
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。

Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态：1表示已建，0表示未建。

当N为0时输入结束。

Output
每个测试用例的输出占一行，输出全省畅通需要的最低成本。

输入样例

3
1 2 1 0
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0
 

输出样例

3
1
0

kruskal的并查集实现
附ac代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int fa[200];
struct cun
{
    int qi;
    int zhi;
    int length;
}c[5100];
bool cmp(cun m,cun n)
{
    return m.length<n.length;
}
int find(int m)
{
    int k,r;
    k=m;
    while(fa[m]!=m)
    {
        m=fa[m];
    }
    //找到最终父节点后讲过程中所以节点的父节点赋值为最终点
    while(fa[k]!=m)
    {
        r=k;
        k=fa[k];
        fa[r]=m;
    }
    return m;
}
void merge(int m,int n)
{
    fa[m]=n;
}
bool pd(int m)
{
    int p=0;//p要置为0 
    for(int i=1;i<=m;++i)
    {if(find(i)==i) p++;
    if(p>1) return 0;
    }
    return 1;
}
void mst(int n)
{
    int n1=n*(n-1)/2;
    sort(c,c+n1,cmp);
    int f1,f2,ans=0;
    for(int i=0;i<n1;++i)
    {
        f1=find(c[i].qi);f2=find(c[i].zhi);
        if(f1!=f2)
        {
        merge(f1,f2);ans+=c[i].length;
        }
    }
    printf("%d\n",ans);
}
int main()
{
    int n;
    bool jian;
    while(scanf("%d",&n)==1)
    {
        if(n==0) break;
        for(int i=1;i<=n;++i) fa[i]=i;
        for(int i=0;i<n*(n-1)/2;++i)
        {scanf("%d%d%d",&c[i].qi,&c[i].zhi,&c[i].length);
        cin>>jian;
        if(jian) merge(c[i].qi,c[i].zhi);
        }
        mst(n);
    }
}