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

一直检查不出来哪里错。高手来看看吧

Posted by bjj at 2011-01-30 18:42:35
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator