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

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

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 69  Solved: 49
[Submit][Status][Discuss]

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

Silver

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

 /**************************************************************
     Problem:
     User: HansBug
     Language: Pascal
     Result: Accepted
     Time: ms
     Memory: kb
 ****************************************************************/

 var
    i,j,k,l,m,n,x,ans:longint;
    a:array[..,..] of longint;
    c:array[..] of longint;
 function getfat(x:longint):longint;
          begin
               if c[x]<>x then c[x]:=getfat(c[x]);
               exit(c[x]);
          end;
 procedure swap(var x,y:longint);
           var z:longint;
           begin
                z:=x;x:=y;y:=z;
           end;
 procedure sort(l,r:longint);
           var i,j,x,y:longint;
           begin
                i:=l;j:=r;x:=a[(l+r) div ,];
                repeat
                      while a[i,]>x do inc(i);
                      while a[j,]<x do dec(j);
                      if i<=j then
                         begin
                              swap(a[i,],a[j,]);
                              swap(a[i,],a[j,]);
                              swap(a[i,],a[j,]);
                              inc(i);dec(j);
                         end;
                until i>j;
                if i<r then sort(i,r);
                if l<j then sort(l,j);
           end;

 {$IFDEF WINDOWS}{$R bzoj3390.rc}{$ENDIF}

 begin
      readln(n,m);
      for i:= to n do c[i]:=i;
      for i:= to m do readln(a[i,],a[i,],a[i,]);
      sort(,m);
      j:=;x:=;
      for i:= to n- do
          begin
               while j<=m do
                     begin
                          k:=getfat(a[j,]);
                          l:=getfat(a[j,]);
                          if k<>l then break;
                          inc(j);
                     end;
               if k=l then break;
               ans:=ans+a[j,];
               c[k]:=l;inc(j);
               inc(x);
          end;
      if x<(n-) then writeln(-) else writeln(ans);
      readln;
 end.