「BZOJ 1585」Earthquake Damage 2 - 最小割

发表于 | 分类于

农场里有 个牧场，有 条无向道路连接着他们，第 条道路连接着两个牧场 和 ，注意可能有很多条道路连接着相同的 和 ，并且 有可能和 相等。Farmer John 在 号牧场里。某些牧场被损坏， 条道路没有一条损坏。有 头奶牛，第 头奶牛报告一个整数 ，代表第 个牧场没有损毁，但不能够从第 个牧场经过一些没有损坏的牧场到达 号牧场。现在 Farmer John 想知道，最少有多少损坏的牧场。

链接

BZOJ 1585

题解

将点拆成两个，之间容量为 。从源点连向每个 ，从 点连向汇点，求出最小割即为答案。

代码

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

const int MAXN = 3000;
const int MAXM = 20000;

struct Node;
struct Edge;

struct Node {
    Edge *e, *c;
    int l;
} N[MAXN * 2 + 2];

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

    Edge(Node *s, Node *t, const int c) : t(t), 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->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->c) {
            int f = findPath(e->t, t, std::min(limit, e->c));
            if (f) {
                e->c -= f, e->r->c += 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 main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);

    const int s = 0, t = n + n + 1;

    for (int i = 1; i <= n; i++) addEdge(i, i + n, 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);

        addEdge(u + n, v, INT_MAX);
        addEdge(v + n, u, INT_MAX);
    }

    for (int i = 0; i < k; i++) {
        int u;
        scanf("%d", &u);

        addEdge(s, u + n, INT_MAX);
    }

    addEdge(1, t, INT_MAX);

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

    return 0;
}