一道网络流的题目。二分时间，然后把每个出口按照时间拆点，每个人向可以到达门的最短时间以后的门节点连一条流量为1的边。源点到所有人连一条流量为1的边，所有门向汇连一条流量为1的边，如果最大流是人的总数则可以逃离，向下二分。
program p1189;
const
h:array[1..4] of longint=(0,1,0,-1);
z:array[1..4] of longint=(1,0,-1,0);
type
bian=record
point,next,f:longint;
end;
arr=array[1..400] of longint;
var
y:array[0..21,0..21] of longint;
x,s,p,dst:array[0..400000] of longint;
pd:array[1..400000] of boolean;
b:array[0..2000000] of bian;
d:array[1..800] of arr;
maxn,last,mid,ans,l,r,q,k1,k2,k,long,len,tot,n,m,i,j:longint;
ch:char;
procedure ade(k1,k2,k3:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
b[len].f:=k3;
p[k1]:=len;
end;
procedure add(k1,k2,k3:longint);
begin
ade(k1,k2,k3);
ade(k2,k1,0);
end;
procedure bfs1(k:longint;var d:arr);
var
i,j,head,now:longint;
begin
fillchar(s,sizeof(s),0);
fillchar(pd,sizeof(pd),false);
head:=1; now:=0; s[1]:=x[k]; d[x[k]]:=0; pd[x[k]]:=true;
while head>now do begin
inc(now);
i:=p[s[now]];
while i<>-1 do begin
j:=b[i].point;
if (pd[j]=false) then begin
inc(head);
pd[j]:=true;
s[head]:=j;
d[j]:=d[s[now]]+1;
end;
i:=b[i].next;
end;
end;
end;
function bfs:boolean;
var
k1,k2,k3,now,head,i,j:longint;
begin
fillchar(pd,sizeof(pd),false);
pd[0]:=true; head:=1; now:=0; s[1]:=0; dst[0]:=0;
while now<head do begin
inc(now);
i:=p[s[now]];
while i>-1 do begin
k1:=b[i].point;
if (pd[k1]=false) and (b[i].f>0) then begin
pd[k1]:=true;
dst[k1]:=dst[s[now]]+1;
if k1=last then exit(true);
inc(head);
s[head]:=k1;
end;
i:=b[i].next;
end;
end;
exit(pd[last]);
end;
function min(k1,k2:longint):longint;
begin
if k1<k2 then exit(k1) else exit(k2);
end;
function change(k1,k2:longint):longint;
var
now,i,j,k:longint;
begin
if (k1=last) or (k2=0) then exit(k2);
now:=p[k1];
j:=0;
while now>-1 do begin
i:=b[now].point;
if (b[now].f>0) and (dst[k1]=dst[i]-1) then begin
k:=change(i,min(b[now].f,k2));
k2:=k2-k;
j:=j+k;
b[now].f:=b[now].f-k;
inc(b[now xor 1].f,k);
if k2=0 then break;
end;
now:=b[now].next;
end;
if j=0 then dst[k1]:=-1;
exit(j);
end;
function dinic:longint;
var
num:longint;
begin
num:=0;
while bfs do
num:=num+change(0,maxlongint);
exit(num);
end;
function find(t:longint):boolean;
var
q,k,k1,k2,i,j:longint;
begin
k:=long*t;
fillchar(p,sizeof(p),-1);
fillchar(b,sizeof(b),0);
len:=-1;
for i:=1 to long do
for j:=1 to n*m do begin
if y[(j-1) div m+1,(j-1) mod m+1]=2 then continue;
for q:=d[i,j] to t do begin
k1:=q*long-long+i;
k2:=k+j;
{ WRITELN(K1,' ',K2,' ',LONG,' ',Q);}
add(k2,k1,1);
end;
end;
for i:=1 to k do
add(i,k+n*m+1,1);
last:=k+n*m+1;
for i:=k+1 to n*m+k do
add(0,i,1);
if dinic=tot then exit(true) else exit(false);
end;
begin
readln(n,m);
fillchar(y,sizeof(y),0);
long:=0;
for i:=1 to n do begin
for j:=1 to m do begin
read(ch);
if ch='.' then y[i,j]:=1
else if ch='D' then begin
inc(long);
x[long]:=i*m-m+j;
y[i,j]:=2;
end;
end;
readln;
end;
fillchar(p,sizeof(p),-1);
fillchar(b,sizeof(b),0);
len:=-1;
for i:=1 to n do
for j:=1 to m do
for k:=1 to 4 do begin
k1:=i+h[k];
k2:=j+z[k];
if (y[i,j]<>0) and (y[k1,k2]<>0) then begin
ade(i*m-m+j,k1*m-m+k2,1);
ade(k1*m-m+k2,i*m-m+j,1);
end;
end;
fillchar(d,sizeof(d),$3f);
maxn:=d[1,1];
for i:=1 to long do
bfs1(i,d[i]);
l:=0;
for i:=1 to long do
for j:=1 to n*m do
if (l<d[i,j]) and (d[i,j]<>maxn) then l:=d[i,j];
r:=0;
for i:=1 to n do
for j:=1 to m do
if y[i,j]=1 then inc(r);
tot:=r;
r:=r+l+1;
l:=1;
if find(r)=false then begin
write('impossible');
exit;
end;
while r>l do begin
mid:=(r+l) div 2;
if find(mid) then begin
r:=mid;
ans:=mid;
end else
l:=mid+1;
end;
writeln(ans);
end.
2023年5月19日 18:39
Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team. jnanabhumiap.in