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.
分享到:
相关推荐
北大POJ1459-Power Network 解题报告+AC代码
poj 1459 Power Network.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告