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

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

  1. 对于点 i ,划给 A 集合得 VA_i 分,划给 B 集合得 VB_i 分;
  2. 对于一条边 i ,若它连接两个 A 集合点,则得 EA_i 分,若它连接两个 B 集合点,则得 EB_i 分,否则将扣除 EC_i 分。

链接

BZOJ 3511

题解

建立最小割模型,使 A 集合的点与 S 连通, B 集合的点与 T 连通。

对于每个点 u ,连边 (S, u) = VA_i ,割掉这条边表示它不被放在 A 集合中;连边 (u, T) = VB_i ,割掉这条边表示它不被放在 B 集合中。

对于已经确定的点 1 和点 n ,连两条容量为正无穷的边 (S, 1) (n, T) ,这两条边都不会被割掉。

对于原图中的每条边,将其转化为容量为 \frac{EA_i}{2} + \frac{EB_i}{2} + EC_i 的双向边,并对于两个端点,连接 (S, u) = \frac{EA_i}{2}, (u, T) = \frac{EB_i}{2}

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

求出最小割即为损失, \sum\limits_{i = 1} ^ {n}(VA_i + VB_i) + \sum\limits_{i = 1} ^ {m}(EA_i + EB_i) 减去损失即为答案。

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

代码

#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;
}