「BZOJ 3438」小 M 的作物 - 最大权闭合图

小 M 有耕地 和 ，有 中作物的种子，第i种作物种植在 中种植可以获得 的收益，在 中种植可以获得 的收益。 共有 种作物组合，第 个组合中的作物共同种在 中可以获得 的额外收益，共同总在 中可以获得 的额外收益。 求最大收益。

链接

BZOJ 3438

题解

首先考虑将所有作物种植在 中，收益为 。

考虑选择一些作物改为种在 中，任意一个作物种在 中后，包含该作物的组合 的 将失去。如果一个组合中所有作物都种在 中，则该组合 的 将被获得。

建立最大权闭合图模型。每个作物的点权为 ，每个组合拆为两个点，一个点表示损失掉的 ，另一个点表示得到的 。

代码

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

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

struct Node;
struct Edge;

struct Node {
    Edge *e, *c;
    int l;
} N[MAXN + MAXM * 2 + 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) {
    // printf("[%d, %d] = %d\n", s, t, 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;
    scanf("%d", &n);

    int sum = 0;

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

    int m;
    scanf("%d", &m);

    const int s = 0, t = n + m * 2 + 1;
    for (int i = 1; i <= n; i++) {
        int w = b[i - 1] - a[i - 1];
        if (w > 0) addEdge(s, i, w), sum += w;
        else addEdge(i, t, -w);
    }

    for (int i = n + 1; i <= n + m; i++) {
        int k, c1, c2;
        scanf("%d %d %d", &k, &c1, &c2);

        addEdge(i, t, c1);
        addEdge(s, i + m, c2);

        sum += c1 + c2;

        for (int j = 0; j < k; j++) {
            int x;
            scanf("%d", &x);
            addEdge(x, i, INT_MAX);
            addEdge(i + m, x, INT_MAX);
        }
    }

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

    return 0;
}