var
 q,incf,link:array[0..2000]of longint;
 vis:array[0..1000]of boolean;
 f:array[0..1000,0..1000]of longint;
 n,p,c,m,i,u,v,s,t,w:longint;
 ch:char;
 str:string;

function maxflow:longint;

 function min(x,y:longint):longint;
  begin
   if x<y then exit(x) else exit(y);
  end;

 function bfs:boolean;
  var
   l,r,u,v:longint;
  begin
   fillchar(q,sizeof(q),0);
   fillchar(vis,sizeof(vis),0);
   fillchar(link,sizeof(link),0);
   fillchar(incf,sizeof(incf),0);
   l:=1; r:=1;
   q[1]:=s; vis[s]:=true;
   link[s]:=s;
   incf[s]:=maxlongint;
   while l<=r do
    begin
     u:=q[l];
      for i:=0 to n+2 do
       if not vis[i] and(f[u,i]>0) then
        begin
         vis[i]:=true;
         inc(r);
         q[r]:=i;
         link[i]:=u;
         incf[i]:=min(incf[u],f[u,i]);
         if i=t then exit(true);
        end;
     inc(l);
    end;
   exit(false);
  end;

 procedure update;
  var
   u,v:longint;
  begin
   u:=t;
   while u<>s do
    begin
     v:=u;
     u:=link[v];
     dec(f[u,v],incf[t]);
     inc(f[v,u],incf[t]);
    end;
   inc(maxflow,incf[t]);
  end;

 begin
  maxflow:=0;
  while bfs do update;
 end;

begin
 repeat
  read(n,p,c,m);
  s:=n+1; t:=n+2;
  fillchar(f,sizeof(f),0);
  for i:=1 to m do
   begin
    repeat read(ch); until ch='(';
    repeat read(ch); str:=str+ch; until ch=',';
    delete(str,length(str),1);
    val(str,u); str:='';
    repeat read(ch); str:=str+ch; until ch=')';
    delete(str,length(str),1);
    val(str,v); str:='';
    read(f[u,v]);
   end;
  for i:=1 to p do
   begin
    repeat read(ch); until ch='(';
    repeat read(ch); str:=str+ch; until ch=')';
    delete(str,length(str),1);
    val(str,u); str:='';
    read(f[s,u]);
   end;
  for i:=1 to c do
   begin
    repeat read(ch); until ch='(';
    repeat read(ch); str:=str+ch; until ch=')';
    delete(str,length(str),1);
    val(str,v); str:='';
    read(f[v,t]);
   end;
  writeln(maxflow);
 until eof;
end.

• Re:为什么会WA？百思不得其解啊。 (2230) lydliyudong 2011-01-25 18:36:13