[HNOI2007]紧急疏散

Description

BZOJ1189

Luogu3191

Solution

看上去很像网络流但是还是不会做啊！！！

正解要二分答案然后网络流判定能否走出去，因为一个时刻只能出去一个人，所以门是有流量限制的，这样看是否满流就行了。

然后建图要注意只有能到的点才向门连边，不要“穿墙”。

UPD:BZOJ的数据好像卡了这种建图方法……所以要把门拆成时刻建图，麻烦的要死……就没有写……

Code

const int N = 410;
const int M = 20 * N * N * 2;
const int INF = 0x3f3f3f3f;

int hd[N], to[M], nxt[M], cap[M], cnt;
int d[N], qhd, qtl, q[N], s, t;
int n, m, id[N][N];
char mp[40][40];

void init() {
    cnt = 1;
    memset(hd, 0, sizeof hd);
    memset(nxt, 0, sizeof nxt);
}
void Adde(int x, int y, int z) {
    to[++cnt] = y;
    cap[cnt] = z;
    nxt[cnt] = hd[x];
    hd[x] = cnt;
}
void adde(int x, int y, int z) {
    Adde(x, y, z);
    Adde(y, x, 0);
}
bool bfs() {
    memset(d, 0, sizeof d);
    qhd = qtl = 0;
    d[q[qtl++] = s] = 1;
    while (qhd != qtl) {
        int x = q[qhd++];
        for (int i = hd[x]; i; i = nxt[i]) {
            if (cap[i] && !d[to[i]]) d[q[qtl++] = to[i]] = d[x] + 1;
        }
        if (d[t]) break;
    }
    return d[t];
}
int dfs(int x, int flw) {
    if (x == t || !flw) return flw;
    int ret = 0;
    for (int i = hd[x]; i; i = nxt[i])
        if (cap[i] && d[to[i]] == d[x] + 1) {
            int tmp = dfs(to[i], std::min(flw, cap[i]));
            if (tmp > 0) {
                ret += tmp;
                flw -= tmp;
                cap[i ^ 1] += tmp;
                cap[i] -= tmp;
            }
        }
    return ret;
}
int dinic() {
    int flw = 0;
    while (bfs()) {
        flw += dfs(s, INF);
    }
    return flw;
}
int vis[N][N];
void adde(int x, int y, int tx, int ty, int mxd) {
    if (abs(tx - x) + abs(ty - y) > mxd || vis[x][y]) return;
    vis[x][y] = 1;
    if (mp[x][y] == '.') adde(id[x][y], id[tx][ty], 1);
    if (mp[x - 1][y] == '.') adde(x - 1, y, tx, ty, mxd);
    if (mp[x + 1][y] == '.') adde(x + 1, y, tx, ty, mxd);
    if (mp[x][y - 1] == '.') adde(x, y - 1, tx, ty, mxd);
    if (mp[x][y + 1] == '.') adde(x, y + 1, tx, ty, mxd);
}
bool check(int x) {
    init();
    int tot = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (mp[i][j] == '.') {
                adde(s, id[i][j], 1);
                tot++;
            } else if (mp[i][j] == 'D') {
                adde(id[i][j], t, x);
                memset(vis, 0, sizeof vis);
                adde(i, j, i, j, x);
            }
        }
    }
    return dinic() == tot;
}

void main() {
    n = read(), m = read();
    s = 0, t = n * m + 1;
    for (int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) id[i][j] = j + (i - 1) * m;
    int l = 0, r = n * m * n * m + 1, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    if (~ans)
        printf("%d
", ans);
    else
        puts("impossible");
}

Note

每次网络流的题都要调好久啊，这样下去不就gg了吗……