POJ 1698 Alive's Chance
Programpoj1698;
constfiftyweeks=350;
typecord=record
po,da,ne:longint;
end;
vartt,i,n,le,s,t,flow,tot:longint;
a:array[1..9]oflongint;
head:array[1..500]oflongint;
link:array[-100000..100000]ofcord;
cur,dis:array[1..500]oflongint;
vh:array[0..500]oflongint;
Procedureadd(x,y,z:longint);
Begin
inc(le);
withlink[le]do
begin
po:=y;da:=z;ne:=head[x];
end;
head[x]:=le;
withlink[-le]do
begin
po:=x;da:=0;ne:=head[y];
end;
head[y]:=-le;
end;
Procedureinit;
vari,j,k:longint;
Begin
le:=0;
flow:=0;tot:=0;
readln(n);
s:=fiftyweeks+n+1;t:=fiftyweeks+n+2;
fillchar(head,sizeof(head),0);
fori:=1tondo
Begin
forj:=1to9doread(a[j]);
add(s,i+fiftyweeks,a[8]);
inc(tot,a[8]);
fork:=1to7do
ifa[k]=1then
forj:=1toa[9]doadd(i+fiftyweeks,(j-1)*7+k,1);
end;
fori:=1tofiftyweeksdo
add(i,t,1);
end;
Functionmin(a,b:longint):longint;
begin
ifa<bthenmin:=aelsemin:=b;
end;
Functionaug(x,nf:longint):longint;
vari,j,l,d,minh,ins:longint;
begin
ifx=tthenexit(nf);
l:=nf;
i:=cur[x];
whilei<>0do
begin
if(link[i].da>0)and(dis[link[i].po]+1=dis[x])then
begin
cur[x]:=i;
d:=aug(link[i].po,min(l,link[i].da));
dec(link[i].da,d);
inc(link[-i].da,d);
dec(l,d);
if(dis[s]=t)or(l=0)thenexit(nf-l);
end;
i:=link[i].ne;
end;
ifl=nfthen
begin
i:=head[x];
minh:=t;
whilei<>0do
begin
if(link[i].da>0)and(dis[link[i].po]<minh)then
begin
minh:=dis[link[i].po];
ins:=i;
end;
i:=link[i].ne;
end;
cur[x]:=ins;
dec(vh[dis[x]]);
ifvh[dis[x]]=0thendis[s]:=t;
dis[x]:=minh+1;
inc(vh[dis[x]]);
end;
aug:=nf-l;
end;
Proceduremain;
vari,j,k:longint;
Begin
fillchar(dis,sizeof(dis),0);
fori:=1totdocur[i]:=head[i];
fillchar(vh,sizeof(vh),0);
vh[0]:=t;
whiledis[s]<tdoinc(flow,aug(s,maxlongint));
ifflow=totthenwriteln('Yes')elsewriteln('No');
end;
Begin
assign(input,'input.in');assign(output,'output.out');
reset(input);rewrite(output);
readln(tt);
fori:=1tottdo
begin
init;
main;
end;
close(input);close(output);
End.
优质内容筛选与推荐>>