题目链接：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;
}