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
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：虽然准确来讲是最大生成树），感觉自己水水哒
/**************************************************************
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.