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啊？USACO的数据都过了！

Posted by Shurikens at 2011-12-09 11:51:34 on Problem 2112
```Program Poj_2112;//by whitetooth;
Const
maxn=250;maxm=15000;
filename='milking';
Var
pre,other,flow              :array[0..maxm] of longint;
last,can,dist,sum,father    :array[0..maxn] of longint;
a                           :array[0..maxn,0..maxn] of longint;
n,m,c,i,s,t,ans             :longint;

Procedure Init;
Var
j                           :longint;
Begin

s:=0;t:=n+m+1;
fillchar(a,sizeof(a),100);

for i:=1 to n+m do
for j:=1 to n+m do
begin
if (a[i,j]=0)and(i<>j) then a[i,j]:=maxlongint shr 1;
end;
End;

Procedure Prepare;
Var
j,k                         :longint;
Begin
for k:=1 to n+m do
for i:=1 to n+m do
for j:=1 to n+m do
if a[i,j]>a[i,k]+a[k,j] then a[i,j]:=a[i,k]+a[k,j];
End;

Procedure In_Path(Var l:longint;p,q,r:longint);
Begin
inc(l);pre[l]:=last[p];last[p]:=l;other[l]:=q;flow[l]:=r;
inc(l);pre[l]:=last[q];last[q]:=l;other[l]:=p;flow[l]:=0;
End;

Function Max_flow:longint;
Var
p,q,inflow,k,min            :longint;
flag                        :boolean;
Begin
max_flow:=0;
for i:=s to t do can[i]:=last[i];
sum[0]:=t+1;
i:=s;
inflow:=maxlongint;

while dist[s]<t+1 do
begin
flag:=false;

p:=can[i];
while p<>-1 do
begin
q:=other[p];
if (flow[p]>0)and(dist[i]=dist[q]+1) then
begin
flag:=true;

if flow[p]<inflow then inflow:=flow[p];

can[i]:=p;
father[q]:=p;
i:=q;

if i=t then
begin
inc(max_flow,inflow);
while i<>s do
begin
p:=father[i];
dec(flow[p],inflow);
inc(flow[p xor 1],inflow);
i:=other[p xor 1];
end;
inflow:=maxlongint;
end;

break;
end;
p:=pre[p];
end;

if flag then continue;

min:=t+1;
p:=last[i];
while p<>-1 do
begin
q:=other[p];
if (flow[p]>0)and(dist[q]<min) then
begin
min:=dist[q];
k:=p;
end;
p:=pre[p];
end;
can[i]:=k;

dec(sum[dist[i]]);
if sum[dist[i]]=0 then break;
dist[i]:=min+1;
inc(sum[dist[i]]);

if i<>s then i:=other[father[i] xor 1];
end;
End;

Function Check(x:longint):boolean;
Var
i,j,l,temp                  :longint;
Begin
fillchar(last,sizeof(last),255);
fillchar(dist,sizeof(dist),0);
fillchar(sum,sizeof(sum),0);
l:=-1;

for i:=1 to n do
for j:=n+1 to n+m do
if a[i,j]<=x then in_path(l,i,j,1);

for i:=1 to n do in_path(l,s,i,c);
for i:=n+1 to n+m do in_path(l,i,t,1);

temp:=max_flow;

if temp=m then exit(true)
else exit(false);
End;

Procedure Main;
Var
j,l,r,mid,max               :longint;
Begin
prepare;

max:=0;
for i:=1 to n do
for j:=n+1 to n+m do
if a[i,j]>max then max:=a[i,j];

l:=0;r:=max;
while l<=r do
begin
mid:=(l+r) shr 1;
if check(mid) then
begin
ans:=mid;
r:=mid-1;
end
else l:=mid+1;
end;
End;

Procedure Print;
Begin
writeln(ans);
End;

Begin
Init;
Main;
Print;
End.

USACO的数据全都过了，交到这里就是WA……```

Followed by: