Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Kruskal算法解2395刷新纪录,用时0MS,求点击,附PASCAL代码program poj2395; type node=record fromv,endv:integer; weight:longint; end; var e:array[1..10000] of node; s:array[1..2000] of integer; n,m,i,j,k,sum:longint; procedure quick(h,r:integer); var i,j:integer; x,t:longint; begin i:=h;j:=r;x:=e[(i+j)div 2].weight; while i<j do begin while e[i].weight<x do inc(i); while e[j].weight>x do dec(j); if i<=j then begin t:=e[i].weight; e[i].weight:=e[j].weight; e[j].weight:=t; t:=e[i].fromv; e[i].fromv:=e[j].fromv; e[j].fromv:=t; t:=e[i].endv; e[i].endv:=e[j].endv; e[j].endv:=t; inc(i); dec(j); end; end; if i<r then quick(i,r); if j>h then quick(h,j); end; function find(v:integer):integer; begin if s[v]=v then find:=v else begin s[v]:=find(s[v]); find:=s[v]; end; end; begin readln(n,m); for i:=1 to m do readln(e[i].fromv,e[i].endv,e[i].weight); quick(1,m); for i:=1 to n do s[i]:=i; i:=1; j:=1; sum:=0; while i<=n-1 do begin if find(e[j].fromv)<>find(e[j].endv) then begin s[find(e[j].fromv)]:=find(e[j].endv); inc(i); if e[j].weight>sum then sum:=e[j].weight; end; inc(j); end; writeln(sum); end. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator