海报自动设计网站,创意设计思维,佛山市网络seo推广公司,cute模板wordpress题意
传送门 AtCoder ABC239G Builder Takahashi
题解
将原图中每个节点拆为入点 v v v 与出点 v ′ v v′#xff0c;对于原图任一边 ( u , v ) (u,v) (u,v) 则 u ′ → v , v → u u\rightarrow v, v\rightarrow u u′→v,v→u 连一条容量为 ∞ \infty ∞ 的边…题意
传送门 AtCoder ABC239G Builder Takahashi
题解
将原图中每个节点拆为入点 v v v 与出点 v ′ v v′对于原图任一边 ( u , v ) (u,v) (u,v) 则 u ′ → v , v → u u\rightarrow v, v\rightarrow u u′→v,v→u 连一条容量为 ∞ \infty ∞ 的边对于原图每一个点 v → v ′ v\rightarrow v v→v′ 连一条容量为 c v c_v cv 的边。此时答案为新图的最小割。
对于最小割集的求解求解最大流后从源点出发在残余网络中 DFS对所有可达的点打上标记最终满足 v v v 被标记而 v ′ v v′ 未被标记的节点则属于最小割集。
#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;};vectorint iter, level;vectorvectorEdge 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);queueint 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;vectorint 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);vectorint 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;
}
