「BZOJ 3511」土地划分 - 最小割

给定一张个点条边的无向连通图，初始时号点属于集合，号点属于集合。现在要将其他点划分进两个集合，并使得评分最高，评分方式如下：

对于点，划给集合得分，划给集合得分；
对于一条边，若它连接两个集合点，则得分，若它连接两个集合点，则得分，否则将扣除分。

链接

BZOJ 3511

题解

建立最小割模型，使集合的点与连通，集合的点与连通。

对于每个点，连边，割掉这条边表示它不被放在集合中；连边，割掉这条边表示它不被放在集合中。

对于已经确定的点和点，连两条容量为正无穷的边和，这两条边都不会被割掉。

对于原图中的每条边，将其转化为容量为的双向边，并对于两个端点，连接。

如果两个端点都在集合中，那么两条容量为的边会被割掉，如果两个端点都在集合中，那么两条容量为的边会被割掉，否则会割掉一条容量为，一条容量为的边，并且中间的边也会被割掉。

求出最小割即为损失，减去损失即为答案。

输入的数字可能有奇数，可以把所有数字乘以二再进行处理。

代码

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

const int MAXN = 10000;
const int MAXM = 40000;

struct Node;
struct Edge;

struct Node {
    Edge *e, *c;
    int l;
} N[MAXN + 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) {}
};

template <typename T, size_t SIZE>
struct MemoryPool {
    char buf[SIZE * sizeof(T)], *cur;

    MemoryPool() : cur(buf) {}

    T *alloc() {
        if (cur == buf + SIZE * sizeof(T)) return (T *)malloc(sizeof(T));
        else {
            T *p = (T *)cur;
            cur += sizeof(T);
            return p;
        }
    }
};

int n, m;
MemoryPool<Edge, MAXM * 5 * 2 + MAXN * 2 * 2> pool;

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 == 0 && 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, 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 > 0) {
                    e->f += f, e->r->f -= f;
                    return f;
                }
            }
        }

        return 0;
    }

    int operator()(const int s, const int t, const int n) {
        int ans = 0;
        while (makeLevelGraph(&N[s], &N[t], n)) {
            int f;
            while ((f = findPath(&N[s], &N[t])) > 0) ans += f;
        }

        return ans;
    }
} dinic;

inline void addEdge(const int s, const int t, const int c, const int rc = 0) {
    N[s].e = &(*(pool.alloc()) = Edge(&N[s], &N[t], c));
    N[t].e = &(*(pool.alloc()) = Edge(&N[t], &N[s], rc));

    N[s].e->r = N[t].e, N[t].e->r = N[s].e;
}

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

    int sum = 0;

    const int s = 0, t = n + 1;
    addEdge(s, 1, INT_MAX), addEdge(n, t, INT_MAX);
    for (int i = 2; i <= n - 1; i++) {
        int va;
        scanf("%d", &va), va *= 2;
        sum += va;
        addEdge(s, i, va);
    }

    for (int i = 2; i <= n - 1; i++) {
        int vb;
        scanf("%d", &vb), vb *= 2;
        sum += vb;
        addEdge(i, t, vb);
    }

    for (int i = 0; i < m; i++) {
        int u, v, ea, eb, ec;
        scanf("%d %d %d %d %d", &u, &v, &ea, &eb, &ec);
        ea *= 2, eb *= 2, ec *= 2;
        sum += ea, sum += eb;

        int c = (ea / 2 + eb / 2 + ec);
        addEdge(u, v, c, c);

        addEdge(s, u, ea / 2), addEdge(s, v, ea / 2);
        addEdge(u, t, eb / 2), addEdge(v, t, eb / 2);
    }

    int minCut = dinic(s, t, n + 2);
    printf("%d\n", (sum - minCut) / 2);

    return 0;
}