看到有题解说二分,但其实不用二分(二分多一个log)。
从小到达枚举时间p,对每个时间给每个door新建一个点i,
从i向T连一条容量为1的边。
从它p-1的i向p的i连一条容量为inf的边,表示更早的人也可以选择。
从所有跟该door距离为p的人向i连一条容量为1的边,表示他从此时开始可以选择了。
如果满流就退出,否则就接着枚举,并保留当前的那个网络。
(一开始从S向每个人连一条容量为1的边)
处理跟该door距离为p的点 就是 一开始从每个door为起点bfs一遍,处理出距离,再存到vector里面。
我还加了一个剪枝,就是如果没有人和这个door距离为p,就不新建点,把原来的点连向T的边的容量+=1。
(由于很久调试不出来,代码加了一些注释。。)
#include<bits/stdc++.h>
using std::vector;
using std::min;
using std::cerr;using std::endl;
const int N=30,inf=100000000;
const int fx[4]={0,-1,0,1},fy[4]={-1,0,1,0};//四个方向
int door[N<<2],d;//d=door的个数
int now[N<<2],nowe[N<<2];//now=当前时间建的点i,nowe=i连向T的边
int n,m,i,j,x,y,need;//need是还需要流的量
int dy[N][N];//dy[i][j]就是(i,j)对应的点
char ch[N][N];
vector<int> st[N<<2][N*N];//st[x][p]表示和door[x]距离为p的点
int q[N*N],head,tail;bool vis[N*N];int g[N*N];//g[x]为x到rt的距离
void bfs(vector<int> *a,int rt)
{
for(;tail>1;--tail)vis[q[tail]]=0;
g[q[tail=1]=rt]=0;
for(head=1;head<=tail;++head)
{
x=q[head];
if(head>1) a[g[x]].push_back(x);
int X=(x-1)/m+1,Y=(x-1)%m+1;
for(i=0;i<4;++i)
{
y=dy[X+fx[i]][Y+fy[i]];
if(vis[y])continue;//vis[0],vis[墙],vis[门]都=1
vis[y]=1;q[++tail]=y;
g[y]=g[x]+1;
}
}
}
namespace kcz
{
const int N=101000,S=N-1,T=N-2;
int n;
int t[N];
struct edge
{
int to,next,f;
}l[1000000];int e=1;
void add_e(int x,int y,int f)
{
l[++e]=(edge){y,t[x],f};t[x]=e;
l[++e]=(edge){x,t[y]};t[y]=e;
}
int q[N],head,tail,i,x,y,g[N],_t[N];//_t是当前弧
bool bfs()
{
q[tail=1]=T;
for(i=1;i<=n;++i) g[i]=inf;g[S]=inf;
for(head=1;head<=tail;++head)
{
x=q[head];_t[x]=t[x];
if(g[x]>=g[S])continue;
for(i=t[x];y=l[i].to;i=l[i].next)
if(l[i^1].f&&g[y]==inf)
{
g[y]=g[x]+1;q[++tail]=y;
}
}
return g[S]!=inf;
}
int dfs(int x,int f0)
{
if(x==T)return f0;
int f=f0;
for(int &i=_t[x];y=l[i].to;i=l[i].next)
if(l[i].f&&g[y]==g[x]-1)
{
int del=dfs(y,min(f,l[i].f));
l[i].f-=del;l[i^1].f+=del;
f-=del;
if(!f)return f0;
}
return f0-f;
}
void solve(int mx)
{
int p;
for(p=1;need&&p<=mx;++p)
{
for(x=1;x<=d;++x)
{
if(!st[x][p].size()){ ++l[nowe[x]].f;continue; }
++n;
if(now[x]) add_e(now[x],++n,inf);
add_e(n,T,1);
now[x]=n;nowe[x]=t[n];
for(j=0;j<st[x][p].size();++j)
add_e(st[x][p][j],n,1);
}
while(bfs())
need-=dfs(S,inf);
}
if(need)puts("impossible");
else printf("%d\n",p-1);
}
};
int main()
{ freopen("1.in","r",stdin);freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
int i,j,x;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
dy[i][j]=++kcz::n;
for(i=1;i<=n;++i)
{scanf("%s",ch[i]+1);
for(j=1;j<=m;++j)
{
x=dy[i][j];
if(ch[i][j]=='X') {vis[x]=1;continue;}
if(ch[i][j]=='D') {door[++d]=x;vis[x]=1;}
else {kcz::add_e(kcz::S,x,1);++need;}
}
}
vis[0]=1;
for(x=1;x<=d;++x)
bfs(st[x],door[x]);
kcz::solve(n*m);
}