【CCF】最优灌溉 最小生成树

【AC】

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>using namespace std;
const int maxn=1e3+;
const int maxm=1e5+;
int n,m;
struct edge{
    int u;
    int v;
    int w;
    bool operator < (const edge& a) const{
        return w<a.w;
    }
}e[*maxm];
int cnt,ans;
int fa[maxn];
int tot;
void init(){
    tot=;
    for(int i=;i<=n;i++) fa[i]=i;
}
void add(int u,int v,int w){
    e[tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
    tot++;
}
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int u,int v,int w){
    int fu=find(u);
    int fv=find(v);
    if(fu!=fv){
        ans+=w;
        cnt++;
        fa[fu]=fv;
    }
}
int work(){
    cnt=;
    ans=;
    sort(e,e+tot);
    for(int i=;i<tot;i++){        int u=e[i].u;
        int v=e[i].v;
        int w=e[i].w;
        merge(u,v,w);
        if(cnt==n-) return ans;
    }
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        init();
        int u,v,w;
        for(int i=;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        int ans=work();
        printf("%d\n",ans);
    }    return ;
}