一道网络流的题目。二分时间，然后把每个出口按照时间拆点，每个人向可以到达门的最短时间以后的门节点连一条流量为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.
评论 (0)
