题目链接
sb错误调了3hour+。。
bfs预处理出每个(.)到每个(D)的最短距离。
二分时间(t)，把每个(D)拆成(t)个点，这(t)个点两两连边，流量(INF)表示(t)个时刻都可以从这个(D)出。
然后枚举所有(.)，再枚举所有(D)，如果距离(dis)小于(t)，就从这个(.)向这个(D)的第(dis)个点连一条流量为(1)的边，表示从这个时刻开始这个(.)可以从这个(D)出。
然后求最大流，如果等于(.)的个数，说明此(t)可行，二分一下即可。
#include <cstdio>
#include <queue>
#include <cstdlib>
#include <cstring>
#define INF 2147483647
using namespace std;
const int MAXN = 300010;
const int N = 440;
const int MAXM = 200010;
char a[N][N];
int b[N][N], c[N][N];
struct point{
int x, y, time;
}Now;
queue <int> q;
queue <point> Q;
struct Edge{
int from, to, next, rest;
}e[MAXM];
int head[MAXN], num = 1, s, t, now, n, m, dis[MAXN];
inline void Add(int from, int to, int flow){
e[++num] = (Edge){ from, to, head[from], flow }; head[from] = num;
e[++num] = (Edge){ to, from, head[to], 0 }; head[to] = num;
}
inline int id(int i, int j){
return (i - 1) * m + j;
}
int re(){
memset(dis, 0, sizeof dis);
q.push(s); dis[s] = 1;
while(q.size()){
now = q.front(); q.pop();
for(int i = head[now]; i; i = e[i].next)
if(e[i].rest && !dis[e[i].to])
dis[e[i].to] = dis[now] + 1, q.push(e[i].to);
}
return dis[t];
}
int find(int u, int flow){
if(u == t || !flow) return flow;
/*if(u == 448){
int xsxs = 1;
}*/
int sum = 0, T;
for(int i = head[u]; i; i = e[i].next)
if(e[i].rest && dis[e[i].to] == dis[u] + 1){
T = find(e[i].to, min(flow - sum, e[i].rest));
e[i].rest -= T; e[i ^ 1].rest += T; sum += T;
}
if(!sum) dis[u] = 0;
return sum;
}
int dinic(){
int ans = 0;
while(re()) ans += find(s, INF);
/*for(int i = 1; i <= num; ++i)
if(e[i].to <= n * m && e[i].from == s)
if(e[i].rest)
printf("%d %d %d
", (e[i].to - 1) / 12 + 1, e[i].to % 12 == 0 ? 12 : e[i].to % 12, e[i].to);
system("pause");*/
return ans;
}
int cnt, tot, l[] = {233, -1, 1, 0, 0}, r[] = {666, 0, 0, -1, 1}, vis[N][N], L, R;
void bfs(int x, int y){
Q.push((point){x, y, 0});
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
vis[i][j] = 0;
vis[x][y] = 1;
while(Q.size()){
Now = Q.front(); Q.pop();
for(int i = 1; i <= 4; ++i){
int X = Now.x + l[i], Y = Now.y + r[i];
if(!X || !Y || X > n || Y > m || a[X][Y] == 'X' || vis[X][Y]) continue;
Q.push((point){X, Y, Now.time + 1});
vis[X][Y] = 1;
if(b[X][Y]) c[id(x, y)][b[X][Y]] = Now.time + 1;
}
}
}
int ans, mid;
int main(){
scanf("%d%d", &n, &m); s = 290000; t = 300001;
for(int i = 1; i <= n; ++i)
scanf("%s", a[i] + 1);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(a[i][j] == 'D')
b[i][j] = ++cnt;
else if(a[i][j] == '.')
++tot;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(a[i][j] == '.')
bfs(i, j);
L = 1; R = 400; ans = -1;
if(tot)
while(L <= R){
mid = (L + R) >> 1;
memset(head, 0, sizeof head);
num = 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
if(a[i][j] == '.'){
Add(s, id(i, j), 1);
for(int k = 1; k <= cnt; ++k){
int d = id(i, j);
if(c[d][k] && c[d][k] <= mid)
Add(d, 400 + cnt * c[d][k] + k, 1);
}
}
for(int i = 1; i <= cnt; ++i)
for(int j = 1; j <= mid; ++j)
Add(400 + cnt * j + i, t, 1), Add(400 + cnt * j + i, 400 + cnt * j + cnt + i, INF);
if(dinic() == tot) ans = mid, R = mid - 1;
else L = mid + 1;
}
if(ans == -1) printf("impossible
");
else printf("%d
", ans);
return 0;
}