Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## WA了千万次，求解释，或大神给个数据

Posted by xqzxqz at 2011-10-06 08:04:46 on Problem 3522
```program mst;
var
x,y,c,f:array [1..600000] of longint;
n,m,i,j,sum,cost,v1,v2,min,max,mm,xx:longint;
procedure qsort(l,r : longint);
var     i,j,xx,tmp  : longint;
begin
i := l; j := r; xx := c[(l+r)div 2];
repeat
while c[i] < xx do inc(i);
while c[j] > xx do dec(j);
if i <= j then
begin
tmp := x[i]; x[i] := x[j]; x[j] := tmp;
tmp := y[i]; y[i] := y[j]; y[j] := tmp;
tmp := c[i]; c[i] := c[j]; c[j] := tmp;
inc(i); dec(j);
end
until i > j;
if l < j then qsort(l,j);
if i < r then qsort(i,r);
end;
function find(i:longint):longint;
begin
if f[i]<>i then find:=find(f[i])
else find:=i;
f[i]:=find
end;
begin
while true do
begin
if (n=0)and(m=0) then halt;
if m=0 then
begin
writeln(-1);
end
else
if n>m+1 then
begin
for i:=1 to m do
writeln(-1);
end
else
begin
for i:=1 to m do
qsort(1,m);
mm:=maxlongint;
xx:=0;
for i:=1 to m-n+2 do
begin
for j:=1 to n-1 do
f[j]:=j;
min:=maxlongint;
max:=-maxlongint;
sum:=0;
for j:=i to m do
begin
v1:=find(x[j]);
v2:=find(y[j]);
if v1<>v2 then
begin
inc(sum);
if c[j]<min then min:=c[j];
if c[j]>max then max:=c[j];
f[v1]:=v2;
if sum=n-1 then break;
end
end;
if (max=-maxlongint)and(min=maxlongint) then
if i=1 then writeln(-1) else
else if mm>max-min then mm:=max-min;
end;
writeln(mm);
end;
end;
end.
```

Followed by: