| ||||||||||
| 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 | |||||||||
一直检查不出来哪里错。高手来看看吧program po;
var
ev,pre,la,lj,fx,d,vd:array[0..6000]of longint;
fl:array[0..6000]of double;
ans:double;
n,m,l,tt,i,j,h,a,b,tot,sy,th:longint;
procedure insertt(a,b:longint;c:double);
begin
inc(tot);
ev[tot]:=b;
fl[tot]:=c;
pre[tot]:=la[a];
la[a]:=tot;
end;
procedure init;
var
i,j:longint;
r:double;
begin
readln(n,m,l);
sy:=n+m+1;
th:=n+m+2;
tot:=0;
fillchar(la,sizeof(la),0);
for i:=1 to n do begin
read(r);
insertt(sy,i,ln(r));
insertt(i,sy,0);
end;
for i:=1 to m do begin
read(r);
insertt(th,n+i,0);
insertt(n+i,th,ln(r));
end;
for i:=1 to l do begin
readln(a,b);
insertt(a,n+b,100000);
insertt(n+b,a,0);
end;
for i:=1 to tot do
if i mod 2=0 then fx[i]:=i-1
else fx[i]:=i+1;
for i:=1 to th do
lj[i]:=la[i];
end;
function dfs(u:longint;flow:double):double;
var
next,t,dans:double;
j:longint;
begin
if u=th then exit(flow);
dans:=0;
j:=lj[u];
while j<>0 do begin
if (fl[j]>1e-8)and(d[u]=d[ev[j]]+1) then begin
next:=flow-dans;
if fl[j]<next then next:=fl[j];
t:=dfs(ev[j],next);
dans:=dans+t;
fl[j]:=fl[j]-t;
fl[fx[j]]:=fl[fx[j]]+t;
if dans>flow-1e-8 then begin
lj[u]:=j;
exit(flow);
end;
end;
j:=pre[j];
end;
dec(vd[d[u]]);
if vd[d[u]]=0 then d[sy]:=th;
inc(d[u]);
inc(vd[d[u]]);
lj[u]:=la[u];
dfs:=dans;
end;
procedure sap;
begin
ans:=0;
fillchar(d,sizeof(d),0);
vd[0]:=th;
while d[sy]<n do begin
// writeln(d[sy]);
ans:=ans+dfs(sy,10000);
end;
end;
procedure work;
begin
init;
sap;
writeln(exp(ans):0:4);
end;
begin
readln(tt);
for h:=1 to tt do work;
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator