HDU-1233 还是畅通工程

传送门：HDU - 1233

题目描述

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入描述

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )
随后的N*(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

输出描述

对每个测试用例，在1行里输出最小的公路总长度。

题意分析

有n个村庄，那么至少需要n-1条线路，要想长度最短，我们可以贪心，每次尽力选择较短的路线，这就需要对所有边的权值进行从小到大排序，判断两个村庄是否已经连通可以通过并查集来解决。

样例输入

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

样例输出

3
5

AC代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef map<ll, ll> mll;

#define ull unsigned long long
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

const int maxn=1e6+10;
const ll mod=1e9+7;
const int INF = 0x3f3f3f3f;
const double pi=acos(-1.0);

int f[10000];

struct node{
    int x,y,m;
}a[10000];

int cmp(node a,node b){
    return a.m<b.m;
}

int find(int x){
    if(f[x]==x)
        return x;
    else
        return f[x]=find(f[x]);

}

int unite(int a,int b){
    int t1,t2;
    t1=find(a);
    t2=find(b);
    if(t1!=t2){
        f[t2]=t1;
        return 1;
    }
    return 0;

}

int main(){
    IOS;
    int n;
    while(cin>>n){
        if(n==0)
            return 0;

        memset(f,0,sizeof(f));
        int cnt,i;
        cnt=n*(n-1)/2;
        for(i=1;i<=cnt;i++){
            cin>>a[i].x>>a[i].y>>a[i].m;
        }
        sort(a+1,a+cnt+1,cmp);
        for(i=1;i<=n;i++)
            f[i]=i;
        int sum=0,ans=0;
        for(i=1;i<=cnt;i++){
            if(unite(a[i].x,a[i].y)){
                sum++;
                ans+=a[i].m;
            }
            if(sum==n-1)
                break;
        }
        cout<<ans<<endl;
    }
}