「BeiJing2006」狼抓兔子 - 最小割

左上角点为 ，右下角点为 ，有以下三种类型的道路：

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

链接

BZOJ 1001

题解

Dinic 模板题，注意注意内存就好 ……

边直接加双向边，反向边的容量和原边相等即可。

代码

#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>

const int MAXN = 1000;
const int MAXM = 1000;

struct Node;
struct Edge;

struct Node {
    Edge *e, *c;
    int l;
} N[MAXN * MAXM + 2];

struct Edge {
    Node *t;
    int c;
    Edge *n, *r;

    Edge(Node *s, Node *t, const int c) : t(t), c(c), n(s->e) {}
};

inline void addEdge(int s, int t, int c) {
    N[s].e = new Edge(&N[s], &N[t], c);
    N[t].e = new Edge(&N[t], &N[s], c);
    N[s].e->r = N[t].e, N[t].e->r = N[s].e;
}

struct Dinic {
    int augment(Node *s, Node *t, const int h = INT_MAX) {
        if (s == t) return h;
        for (Edge *&e = s->c; e; e = e->n) {
            if (e->c > 0 && e->t->l == s->l + 1) {
                int f = augment(e->t, t, std::min(e->c, h));
                if (f) {
                    e->c -= f, e->r->c += f;
                    return f;
                }
            }
        }

        return 0;
    }

    int operator()(const int s, const int t, const int n) {
        int r = 0;
        while (1) {
            for (int i = 0; i < n; i++) N[i].l = 0, N[i].c = N[i].e;

            bool f = false;
            std::queue<Node *> q;
            q.push(&N[s]), N[s].l = 1;
            while (!q.empty()) {
                Node *v = q.front();
                q.pop();
                for (Edge *e = v->e; e; e = e->n)
                    if (!e->t->l && e->c > 0) {
                        e->t->l = v->l + 1;
                        if (e->t == &N[t]) {
                            f = true;
                            break;
                        } else q.push(e->t);
                    }
            }
            if (!f) return r;

            for (int f; f = augment(&N[s], &N[t]); r += f);
        }
    }
} dinic;

int n, m;

inline int id(const int i, const int j) {
    return (i - 1) * m + j;
}

int main() {
    scanf("%d %d", &n, &m);

    const int s = 0, t = n * m + 1;
    addEdge(s, id(1, 1), INT_MAX), addEdge(id(n, m), t, INT_MAX);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m - 1; j++) {
            int c;
            scanf("%d", &c);
            addEdge(id(i, j), id(i, j + 1), c);
        }
    }

    for (int i = 1; i <= n - 1; i++) {
        for (int j = 1; j <= m; j++) {
            int c;
            scanf("%d", &c);
            addEdge(id(i, j), id(i + 1, j), c);
        }
    }

    for (int i = 1; i <= n - 1; i++) {
        for (int j = 1; j <= m - 1; j++) {
            int c;
            scanf("%d", &c);
            addEdge(id(i, j), id(i + 1, j + 1), c);
        }
    }

    printf("%d\n", dinic(s, t, n * m + 2));

    return 0;
}