3390: [Usaco2004 Dec]Bad Cowtractors牛的报复

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 69  Solved: 49

[][][]

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

连接4和5,2和5，2和3，1和3，花费17+8+10+7=42

HINT

 

Source

 

题解：最小生成树模板题（HansBug：虽然准确来讲是最大生成树），感觉自己水水哒

1 /************************************************************** 2     Problem: 3390 3     User: HansBug 4     Language: Pascal 5     Result: Accepted 6     Time:56 ms 7     Memory:1788 kb 8 ****************************************************************/ 9  10 var11    i,j,k,l,m,n,x,ans:longint;12    a:array[0..100005,1..3] of longint;13    c:array[0..100005] of longint;14 function getfat(x:longint):longint;15          begin16               if c[x]<>x then c[x]:=getfat(c[x]);17               exit(c[x]);18          end;19 procedure swap(var x,y:longint);20           var z:longint;21           begin22                z:=x;x:=y;y:=z;23           end;24 procedure sort(l,r:longint);25           var i,j,x,y:longint;26           begin27                i:=l;j:=r;x:=a[(l+r) div 2,3];28                repeat29                      while a[i,3]>x do inc(i);30                      while a[j,3]
      
       j;39                if i
       
        l then break;58                          inc(j);59                     end;60               if k=l then break;61               ans:=ans+a[j,3];62               c[k]:=l;inc(j);63               inc(x);64          end;65      if x<(n-1) then writeln(-1) else writeln(ans);66      readln;67 end.