内容目录
hllp写到最后写成预留推进了……
Program P1459; var n,np,nc,m,i,j,src,t,level:longint; ch:char; s:string; d,e,pre:array[-1..100] of longint; map,f:array[-1..100,-1..100] of longint; queue:array[1..102] of longint; list:array[0..103,0..102] of longint; b:array[-1..100] of boolean; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; procedure hllp; var i,j,maxflow,flow,minj:longint; h,t:longint; tag:boolean; begin level:=0; maxflow:=0; flow:=0; h:=1; t:=1; queue[h]:=n; while h<=t do begin for i:=0 to n-1 do if (map[i,queue[h]]>0) and (not(b[i])) then begin inc(t); queue[t]:=i; d[i]:=d[queue[h]]+1; b[i]:=true; end; inc(h); end; d[-1]:=n+2; { for i:=0 to n-1 do if e[i]>0 then begin inc(list[d[i],0]); list[d[i],list[d[i],0]]:=i; level:=max(level,d[i]); end; } while (true) do begin i:=n; for j:=0 to n-1 do begin if (e[j]>0) and (d[j]>d[i]) then i:=j; end; if i=n then break; { i:=list[level,list[level,0]]; dec(list[level,0]); while (level>0) and (list[level,0]=0) do dec(level); } tag:=false; for j:=-1 to n do begin if e[i]=0 then break; if (d[i]=d[j]+1) and (map[i,j]-f[i,j]>0) then begin tag:=true; flow:=min(map[i,j]-f[i,j],e[i]); dec(e[i],flow); inc(e[j],flow); inc(f[i,j],flow); f[j,i]:=-f[i,j]; end; end; if (e[i]>0) then begin minj:=maxlongint; for j:=-1 to n do if (map[i,j]-f[i,j]>0) {and (d[i]>=d[j])} then minj:=min(minj,d[j]); { if minj=maxlongint then begin e[i]:=0; continue; end; } d[i]:=minj+1; end; end; end; function isdight(a:char):boolean; begin if (48<=ord(a)) and (ord(a)<=57) then exit(true) else exit(false); end; procedure rea(var a:longint); var ch:char; s:string; begin ch:=' '; while not(isdight(ch)) do read(ch); s:=''; repeat s:=s+ch; read(ch); until not(isdight(ch)); val(s,a); end; begin { assign(input,'p1459.in'); assign(output,'p1459.out'); reset(input); rewrite(output); } while not seekeof do begin fillchar(map,sizeof(map),0); fillchar(e,sizeof(e),0); fillchar(f,sizeof(f),0); fillchar(list,sizeof(list),0); fillchar(d,sizeof(d),0); fillchar(b,sizeof(b),false); rea(n); for i:=-1 to n do pre[i]:=i; rea(np); rea(nc); rea(m); for i:=1 to m do begin rea(src); rea(t); rea(map[src,t]); end; for i:=1 to np do begin rea(t); rea(map[-1,t]); e[t]:=map[-1,t]; f[-1,t]:=map[-1,t]; f[t,-1]:=-map[-1,t]; end; for i:=1 to nc do begin rea(src); rea(map[src,n]); end; hllp; writeln(e[n]); end; { close(input); close(output); } end.