「BZOJ 3894」文理分科 - 最大权闭合图

小 P 所在的班级要进行文理分科。他的班级可以用一个的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：

如果第行第列的同学选择了文科，则他将获得的满意值，如果选择理科，将获得的满意值。
如果第行第列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加的满意值。
如果第行第列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加的满意值。

小 P 想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。

链接

题解

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

建立最大权闭合图模型：为每个人建个点，分别表示 TA 自己改选理科（权值为）、TA 和 TA 相邻的人有任意一个选择理科（失去文科的收益加成）、TA 和 TA 相邻的人全部选择理科（获得理科的收益加成）。对于每一个人，从TA 和 TA 相邻所有人的第一个点向 TA 的第二个点连边，从 TA 的第三个点向 TA 和 TA 相邻所有人的第一个点连边。

代码

#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 * 3 + 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], A[MAXN][MAXN], B[MAXN][MAXN], id[MAXN][MAXN][3];

    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; 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]);

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

    const int s = 0, t = n * m * 3 + 1;

    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, id[i][j][0], x), sum += x;
            else addEdge(id[i][j][0], t, -x);
            addEdge(id[i][j][1], t, A[i][j]);
            addEdge(s, id[i][j][2], B[i][j]), sum += B[i][j];

            addEdge(id[i][j][0], id[i][j][1], INT_MAX);
            addEdge(id[i][j][2], id[i][j][0], INT_MAX);

            if (i != 0) {
                addEdge(id[i][j][0], id[i - 1][j][1], INT_MAX);
                addEdge(id[i - 1][j][2], id[i][j][0], INT_MAX);
            }

            if (i != n - 1) {
                addEdge(id[i][j][0], id[i + 1][j][1], INT_MAX);
                addEdge(id[i + 1][j][2], id[i][j][0], INT_MAX);
            }

            if (j != 0) {
                addEdge(id[i][j][0], id[i][j - 1][1], INT_MAX);
                addEdge(id[i][j - 1][2], id[i][j][0], INT_MAX);
            }

            if (j != m - 1) {
                addEdge(id[i][j][0], id[i][j + 1][1], INT_MAX);
                addEdge(id[i][j + 1][2], id[i][j][0], INT_MAX);
            }
        }
    }

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

    return 0;
}