「BZOJ 2132」圈地计划 - 最小割

发表于 | 分类于

对于第 行第 列的区域，建造商业区将得到 收益，建造工业区将得到 收益。另外不同的区域连在一起可以得到额外的收益，即如果区域 相邻（相邻是指两个格子有公共边）有 块（显然 不超过 ）类型不同于 的区域，则这块区域能增加 收益。求最大收益。

链接

BZOJ 2132

题解

黑白染色，从源点到所有 点连边，容量为 ，从源点到所有 点连边，容量为 ；从所有 点到汇点连边，容量为 ，从所有 点向汇点连边，容量为 。

对于相邻的点，之间连一条容量为 的无向边。

考虑相邻的两个点，如果都割源点方向的边或都割汇点方向的边，则不需要割中间的边；如果一个割源点方向的边，另一个割汇点方向的边，则需要同时割掉中间的边，此时两个点对应区域建造相同。

所有可能获得的收益减去最小割即为答案。

代码

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

const int MAXN = 100;

struct Node;
struct Edge;

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

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

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

struct Dinic {
    bool makeLevelGraph(Node *s, Node *t, const int n) {
        for (int i = 0; i < n; i++) N[i].l = 0, N[i].c = N[i].e;

        std::queue<Node *> q;
        q.push(s);

        s->l = 1;

        while (!q.empty()) {
            Node *v = q.front();
            q.pop();

            for (Edge *e = v->e; e; e = e->next) if (!e->t->l && e->c) {
                e->t->l = v->l + 1;
                if (e->t == t) return true;
                else q.push(e->t);
            }
        }

        return false;
    }

    int findPath(Node *s, Node *t, const int limit = INT_MAX) {
        if (s == t) return limit;

        for (Edge *&e = s->c; e; e = e->next) if (e->t->l == s->l + 1 && e->c) {
            int f = findPath(e->t, t, std::min(limit, e->c));
            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 res = 0;
        while (makeLevelGraph(&N[s], &N[t], n)) {
            int f;
            while ((f = findPath(&N[s], &N[t])) > 0) res += f;
        }

        return res;
    }
} dinic;

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

int n, m;

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

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

    int sum = 0;
    const int s = 0, t = n * m + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            scanf("%d", &x);

            sum += x;

            if ((i + j) % 2 == 0) addEdge(s, id(i, j), x);
            else addEdge(id(i, j), t, x);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            scanf("%d", &x);

            sum += x;

            if ((i + j) % 2 != 0) addEdge(s, id(i, j), x);
            else addEdge(id(i, j), t, x);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            scanf("%d", &x);

            if (i != 1) addEdge(id(i - 1, j), id(i, j), x, x), sum += x;
            if (i != n) addEdge(id(i + 1, j), id(i, j), x, x), sum += x;
            if (j != 1) addEdge(id(i, j - 1), id(i, j), x, x), sum += x;
            if (j != m) addEdge(id(i, j + 1), id(i, j), x, x), sum += x;
        }
    }

    const int maxFlow = dinic(s, t, n * m + 2);
    printf("%d\n", sum - maxFlow);

    return 0;
}