「BJOI 2006」狼抓兔子

题目链接:BZOJ 1001

现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:

左上角点为 $(1,1)$,右下角点为 $(n,m)$(上图中 $n=3, m=4​$)。有以下三种类型的道路:

  1. $(x,y)\longleftrightarrow(x+1,y)$
  2. $(x,y)\longleftrightarrow(x,y+1)$
  3. $(x,y)\longleftrightarrow(x+1,y+1)$

道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的。左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角 $(1,1)$ 的窝里,现在它们要跑到右下角 $(n,m)$ 的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为 $k$,狼王需要安排同样数量的 $k$ 只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。

数据范围:$1\le n, m\le 1000$。


Solution

很显然是一个裸的最小割,对 $(1,1)$ 到 $(n,m)$ 依次编号,然后按照题意建边跑最短路即可 QAQ

吐槽:终于做出了 BZOJ 的 1001(大雾

当然由于这题的图是一张平面图,所以我们也可以建出对偶图,直接跑最短路,得到的就是原图的最小割。

时间复杂度:$\mathcal O((nm)^3)$。


Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 1e6 + 5, M = 6e6 + 5;
const int INF = 0x3f3f3f3f;

int n, m, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N];

int id(int x, int y) {
    return (x - 1) * m + y;
}
void add(int u, int v, int w) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w;
}
void addEdge(int u, int v, int w) {
    add(u, v, w), add(v, u, w);
}
int bfs(int s, int t) {
    memset(dep, 0, sizeof(dep));
    memcpy(cur, lnk, sizeof(lnk));
    std::queue<int> q;
    q.push(s), dep[s] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (val[i] && !dep[v]) {
                q.push(v), dep[v] = dep[u] + 1;
            }
        }
    }
    return dep[t];
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    int ans = 0;
    for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
        int v = ter[i];
        if (val[i] && dep[v] == dep[u] + 1) {
            int x = dfs(v, t, std::min(val[i], flow - ans));
            if (x) {
                val[i] -= x, val[i ^ 1] += x, ans += x;
            }
        }
    }
    if (ans < flow) dep[u] = -1;
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) ans += x;
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            int x;
            scanf("%d", &x);
            addEdge(id(i, j), id(i, j + 1), x);
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            scanf("%d", &x);
            addEdge(id(i, j), id(i + 1, j), x);
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            int x;
            scanf("%d", &x);
            addEdge(id(i, j), id(i + 1, j + 1), x);
        }
    }
    printf("%d\n", dinic(id(1, 1), id(n, m)));
    return 0;
}

发表评论