bzoj3390[Usaco2004 Dec]Bad Cowtractors

​​http://www.elijahqi.win/archives/1018​​​

Description

奶牛貝茜被雇去建設N(2≤N≤1000)個牛棚間的網際網路．她已經勘探出M(1≤M≤

20000)條可建的線路，每條線路連接配接兩個牛棚，而且會苞費C(1≤C≤100000)．農夫約翰吝啬得很，他希望建設費用最少甚至他都不想給貝茜工錢． 貝茜得知工錢要告吹，決定報複．她打算選擇建一些線路，把所有牛棚連接配接在一起，讓約翰花費最大．但是她不能造出環來，這樣約翰就會發現．

Input

第1行：N，M.

第2到M+1行：三個整數，表示一條可能線路的兩個端點和費用．

Output

最大的花費．如果不能建成合理的線路，就輸出-1

Sample Input

5 8

1 2 3

1 3 7

2 3 10

2 4 4

2 5 8

3 4 6

3 5 2

4 5 17

Sample Output

42

#include<cstdio>
#include<algorithm>
#define N 1100
#define M 22000
using namespace std;
inline int read(){
    int x=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
struct node{
    int x,y,z,next;
}data[M];
inline bool cmp(node a,node b){return a.z>b.z;}
int n,m,fa[N],h[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
    freopen("bzoj3390.in","r",stdin);
    n=read();m=read();
    for (int i=1;i<=m;++i){
        int x=read(),y=read(),z=read();
        data[i].y=y;data[i].next=h[x];data[i].z=z;h[x]=i;data[i].x=x;
    }
    sort(data+1,data+m+1,cmp);
    for (int i=1;i<=n;++i) fa[i]=i;int ans=0;int cnt=0;
    for (int i=1;i<=m;++i){
        int x=data[i].x,y=data[i].y;
        int xx=find(x),yy=find(y);
        if (xx!=yy){
            ans+=data[i].z;fa[xx]=yy;cnt++;
            if (cnt==n-1){
                printf("%d",ans);break;
            }
        }
    }
    if (cnt<n-1) printf("-1");
    return 0;
}