AtCoder ABC239G 最小割集

题意

传送门 AtCoder ABC239G Builder Takahashi

题解

将原图中每个节点拆为入点 $v$ 与出点 $v^{\prime }$，对于原图任一边 $(u,v)$ 则 $u^{\prime }\to v,v\to u$ 连一条容量为 $\infty$ 的边，对于原图每一个点，$v\to v^{\prime }$ 连一条容量为 $c_v$ 的边。此时答案为新图的最小割。

对于最小割集的求解，求解最大流后，从源点出发在残余网络中 DFS，对所有可达的点打上标记，最终满足 $v$ 被标记而 $v^{\prime }$ 未被标记的节点则属于最小割集。

#include 
using namespace std;
using ll = long long;
constexpr ll INF = 1e18;
struct MaxFlow {
    struct Edge {
        int to;
        ll cap;
        int rev;
    };
    vector<int> iter, level;
    vector<vector<Edge>> g;
    MaxFlow(int n) : iter(n), level(n), g(n) {}
    void add_edge(int from, int to, ll cap) {
        g[from].push_back({to, cap, (int)g[to].size()});
        g[to].push_back({from, 0, (int)g[from].size() - 1});
    }
    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto [to, cap, _] : g[v]) {
                if (cap > 0 && level[to] == -1) {
                    level[to] = level[v] + 1;
                    q.push(to);
                }
            }
        }
    }
    ll dfs(int v, int t, ll f) {
        if (v == t) {
            return f;
        }
        for (int &i = iter[v]; i < (int)g[v].size(); ++i) {
            auto &e = g[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    ll max_flow(int s, int t) {
        ll flow = 0;
        for (;;) {
            fill(iter.begin(), iter.end(), 0);
            bfs(s);
            if (level[t] == -1) {
                return flow;
            }
            ll f;
            while ((f = dfs(s, t, INF)) > 0) {
                flow += f;
            }
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    MaxFlow flow(n * 2);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u -= 1, v -= 1;
        flow.add_edge(v + n, u, INF);
        flow.add_edge(u + n, v, INF);
    }
    for (int v = 0; v < n; ++v) {
        int c;
        cin >> c;
        flow.add_edge(v, v + n, c);
    }
    cout << flow.max_flow(0 + n, n - 1) << '\n';
    vector<int> used(2 * n);
    auto dfs = [&](auto dfs, int v) -> void {
        used[v] = 1;
        for (auto [to, cap, _] : flow.g[v]) {
            if (cap > 0 && !used[to]) {
                dfs(dfs, to);
            }
        }
    };
    dfs(dfs, 0 + n);
    vector<int> vs;
    for (int v = 0; v < n; ++v) {
        if (used[v] && !used[v + n]) {
            vs.push_back(v);
        }
    }
    cout << (int)vs.size() << '\n';
    for (int v : vs) {
        cout << v + 1 << ' ';
    }
    cout << '\n';

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109