# [BZOJ1189]&&[HNOI2007] 紧急疏散 evacuate

12 12
XXXXXDXXXXXX
X…..X….X
X..X..X….X
X…..XXX..X
X…..X….X
XXXXXX…..D
X…..XXXXXX
D….X…..X
D….X…..D
D….XXXXXXX
X….X…..X
XXXXXXXDXXXX

## 样例输出 SampleOutput

19

BZOJ 1189

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int inf = 0x7fffffff / 27.11;
const int maxn = 25 * 25;
const int maxm = 5 * maxn * maxn;
const int dx[5] = {0, 0, 0, 1, -1};
const int dy[5] = {0, 1, -1, 0, 0};
int i, j, t, n, m, l, r, k, z, y, x;
struct edge
{
int to, fl, ds, cap, nx;
} e[maxm];
char a[25][25];
bool b[25][25], c[25][25];
int num[25][25];
int cnt, cntp, cntd, mid, sum, tim;
struct point
{
int x, y, z;
};
vector <point> d;
deque <point> p;
deque <int> q;
inline void ins(int u, int v, int f, int d, int c)
{
e[cnt] = (edge)
{
e[cnt] = (edge)
{
}
inline void find(int sx, int sy)
{
int i, x, y, z;
while (!p.empty()) p.pop_front();
p.push_back((point)
{
sx, sy, 0
});
while (!p.empty())
{
for (i = 1; i <= 4; i++)
{
x = p.front().x + dx[i]; y = p.front().y + dy[i]; z = p.front().z + 1;
if (!b[x][y] && a[x][y] == '.')
{
b[x][y] = true;
c[x][y] = true;
ins(num[x][y], num[sx][sy] + cntp, 1, z, 1);
p.push_back((point)
{
x, y, z
});
}
}
p.pop_front();
}
}
inline bool bfs(int s, int t, int tim)
{
int i, u, v;
while (!q.empty()) q.pop_front();
dis[s] = 0; used[s] = tim;
q.push_back(s);
while (!q.empty())
{
u = q.front(); q.pop_front();
for (i = head[u]; i != -1; i = e[i].nx) if (e[i].ds <= mid)
{
v = e[i].to;
if (used[v] != tim && e[i].fl > 0)
{
used[v] = tim;
dis[v] = dis[u] + 1;
q.push_back(v);
}
}
}
return (used[t] == tim);
}
int dfs(int u, int t, int flow)
{
int i, v, d, k;
if (u == t) return flow;
for (d = flow, i = cur[u]; i != -1; i = e[i].nx) if (e[i].ds <= mid)
{
v = e[i].to;
if (dis[v] == dis[u] + 1 && e[i].fl > 0)
{
k = dfs(v, t, min(d, e[i].fl));
e[i].fl -= k; e[i ^ 1].fl += k;
d -= k;
if (d == 0) break;
}
}
return flow - d;
}
inline bool dinic(int s, int t, int lim)
{
int i, ans = 0;
for (i = 0; i < cnt; i++) e[i].fl = (e[i].cap == -1) ? lim : e[i].cap;
while (bfs(s, t, ++tim))
{
ans += dfs(s, t, inf);
}
return (ans == sum);
}
int main()
{
sum = cnt = cntp = cntd = tim = 0;
memset(c, false, sizeof(c));
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
a[i][j] = getchar();
while (a[i][j] != 'X' && a[i][j] != '.' && a[i][j] != 'D') a[i][j] = getchar();
if (a[i][j] == 'D') d.push_back((point)
{
i, j, 0
}), num[i][j] = ++cntd;
if (a[i][j] == '.') num[i][j] = ++cntp, ins(0, cntp, 1, 0, 1), sum++;
}
}
for (i = 0; i < d.size(); i++)
{
memset(b, false, sizeof(b));
find(d[i].x, d[i].y);
d[i].z = cnt; ins(num[d[i].x][d[i].y] + cntp, cntp + cntd + 1, 0, 0, -1);
}
for (i = 1; i <= n; i++) for (j = 1; j <= m; j++) if (a[i][j] == '.' && !c[i][j])
{
printf("impossible\n");
return 0;
}
l = 0; r = 20 * 20 * 20;
while (r > l)
{
mid = (l + r) >> 1;
if (dinic(0, cntp + cntd + 1, mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
return 0;
}``````