struct Edge { int to, rev; int cap; bool is_cut; // 标记是否为割边 }; class MinCut { private: std::vector G[MAXN]; int level[MAXN]; int iter[MAXN]; public: // 添加一条从from到to,容量为cap的边 void addEdge(int from, int to, int cap) { G[from].push_back({to, (int)G[to].size(), cap, false}); G[to].push_back({from, (int)G[from].size() - 1, 0, false}); } // 构建层次图 bool bfs(int s, int t) { memset(level, -1, sizeof(level)); std::queue q; level[s] = 0; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); for (const auto& e : G[v]) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } return level[t] != -1; } // 在层次图上寻找增广路 int dfs(int v, int t, int upTo) { if (v == t) return upTo; for (int &i = iter[v]; i < G[v].size(); ++i) { Edge &e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, std::min(upTo, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } // 求最大流 int maxFlow(int s, int t) { int flow = 0; while (bfs(s, t)) { memset(iter, 0, sizeof(iter)); int f; while ((f = dfs(s, t, INF)) > 0) { flow += f; } } return flow; } // 获取最小割的割边集合 std::vector> getMinCutEdges(int s) { std::vector> cutEdges; bool vis[MAXN] = {0}; std::queue q; q.push(s); vis[s] = true; while (!q.empty()) { int v = q.front(); q.pop(); for (const auto& e : G[v]) { if (e.cap > 0 && !vis[e.to]) { vis[e.to] = true; q.push(e.to); } } } // 割边:从S集合到T集合的满流边 for (int u = 0; u < MAXN; ++u) { if (vis[u]) { for (const auto& e : G[u]) { if (!vis[e.to] && G[e.to][e.rev].cap > 0) { cutEdges.emplace_back(u, e.to); } } } } return cutEdges; } // 清空图 void clear(int n) { for (int i = 0; i <= n; ++i) G[i].clear(); } };