裸的最小生成树。
/************************************************************** Problem: 1083 User: BLADEVIL Language: Pascal Result: Accepted Time:44 ms Memory:344 kb ****************************************************************/ //By BLADEVIL var n, m :longint; pre, succ, len :array[0..10010] of longint; father :array[0..400] of longint; ans :longint; procedure swap(var a,b:longint); var c :longint; begin c:=a; a:=b; b:=c; end; procedure qs(low,high:longint); var i, j :longint; xx :longint; begin i:=low; j:=high; xx:=len[(i+j)>>1]; while i<j do begin while xx>len[i] do inc(i); while xx<len[j] do dec(j); if i<=j then begin swap(succ[i],succ[j]); swap(pre[i],pre[j]); swap(len[i],len[j]); inc(i); dec(j); end; end; if i<high then qs(i,high); if j>low then qs(low,j); end; procedure init; var i :longint; begin read(n,m); for i:=1 to m do read(pre[i],succ[i],len[i]); qs(1,m); end; function getfather(x:longint):longint; begin if father[x]=x then exit(x); father[x]:=getfather(father[x]); exit(father[x]); end; procedure main; var i :longint; a, b, fa, fb :longint; begin for i:=1 to n do father[i]:=i; for i:=1 to m do begin a:=pre[i]; b:=succ[i]; fa:=getfather(a); fb:=getfather(b); if fa<>fb then begin ans:=len[i]; father[fa]:=fb; end; end; writeln(n-1,‘ ‘,ans); end; begin init; main; end.