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 <bits/stdc++.h>
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;
}