「BZOJ 2127」happiness - 最大权闭合图

发表于 | 分类于

高一一班的座位表是个 的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。如何分配可以使得全班的喜悦值总和最大？

链接

BZOJ 2127

题解

先考虑每个人都选择文科，然后考虑一个人改选理科带来的影响。

建立最大权闭合图模型：为每个人建点，权值为理科收益减去文科收益。为每一对之间建两个点，一个点表示两个人中任意一个人选理，则文科收益加成取消，另一个点表示两个人都选理，则获得理科收益加成。从每一对的第一个点向两个人连边，每个人向每一对的第二个点连边。

代码

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

const int MAXN = 100;

struct Node;
struct Edge;

struct Node {
    Edge *e, *c;
    int l;
} N[MAXN * MAXN + MAXN * (MAXN - 1) * 4 + 2];

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

    Edge(Node *s, Node *t, const int c) : s(s), t(t), f(0), 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->f < 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->f < e->c) {
            int f = findPath(e->t, t, std::min(limit, e->c - e->f));
            if (f) {
                e->f += f, e->r->f -= 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) {
    N[s].e = new Edge(&N[s], &N[t], c);
    N[t].e = new Edge(&N[t], &N[s], 0);
    (N[s].e->r = N[t].e)->r = N[s].e;
}

int s, t;

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

    static int a[MAXN][MAXN], b[MAXN][MAXN], aDown[MAXN - 1][MAXN], bDown[MAXN - 1][MAXN], aRight[MAXN][MAXN - 1], bRight[MAXN][MAXN - 1], vID[MAXN][MAXN], eID[MAXN][MAXN][2][2];
    const int DOWN = 0, RIGHT = 1;

    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &a[i][j]), sum += a[i][j];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &b[i][j]);

    for (int i = 0; i < n - 1; i++) for (int j = 0; j < m; j++) scanf("%d", &aDown[i][j]), sum += aDown[i][j];
    for (int i = 0; i < n - 1; i++) for (int j = 0; j < m; j++) scanf("%d", &bDown[i][j]);

    for (int i = 0; i < n; i++) for (int j = 0; j < m - 1; j++) scanf("%d", &aRight[i][j]), sum += aRight[i][j];
    for (int i = 0; i < n; i++) for (int j = 0; j < m - 1; j++) scanf("%d", &bRight[i][j]);

    int id = 1;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) vID[i][j] = id++;

    // printf("eID starts from %d\n", id);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i != n - 1) eID[i][j][DOWN][0] = id++, eID[i][j][DOWN][1] = id++;
            if (j != m - 1) eID[i][j][RIGHT][0] = id++, eID[i][j][RIGHT][1] = id++;
        }
    }

    const int s = 0, t = n * m + (n * (m - 1) + m * (n - 1)) * 2 + 1;

    // printf("%d %d\n", id, t);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x = b[i][j] - a[i][j];
            if (x > 0) addEdge(s, vID[i][j], x), sum += x;
            else addEdge(vID[i][j], t, -x);

            if (i != n - 1) {
                addEdge(eID[i][j][DOWN][0], t, aDown[i][j]);
                addEdge(s, eID[i][j][DOWN][1], bDown[i][j]), sum += bDown[i][j];

                addEdge(vID[i][j], eID[i][j][DOWN][0], INT_MAX);
                addEdge(vID[i + 1][j], eID[i][j][DOWN][0], INT_MAX);

                addEdge(eID[i][j][DOWN][1], vID[i][j], INT_MAX);
                addEdge(eID[i][j][DOWN][1], vID[i + 1][j], INT_MAX);
            }

            if (j != m - 1) {
                addEdge(eID[i][j][RIGHT][0], t, aRight[i][j]);
                addEdge(s, eID[i][j][RIGHT][1], bRight[i][j]), sum += bRight[i][j];

                addEdge(vID[i][j], eID[i][j][RIGHT][0], INT_MAX);
                addEdge(vID[i][j + 1], eID[i][j][RIGHT][0], INT_MAX);

                addEdge(eID[i][j][RIGHT][1], vID[i][j], INT_MAX);
                addEdge(eID[i][j][RIGHT][1], vID[i][j + 1], INT_MAX);
            }
        }
    }

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

    return 0;
}