Dinic's algorithm
unknown
c_cpp
3 years ago
2.0 kB
6
Indexable
struct max_flow_graph { struct edge { int u, v, cap, flow; }; int n; vector<edge> el; vector<vector<int>> adj; vector<int> dist, par; max_flow_graph(int n) : n(n), adj(n) {} void add_edge(int u, int v, int w) { adj[u].push_back(el.size()); el.push_back({u, v, w, 0}); adj[v].push_back(el.size()); el.push_back({v, u, 0, 0}); } int send_one_flow(int s, int e) { int nf = INF; for (int u = e; u != s; u = el[par[u]].u) { nf = min(nf, el[par[u]].cap - el[par[u]].flow); } for (int u = e; u != s; u = el[par[u]].u) { el[par[u]].flow += nf; el[par[u]^1].flow -= nf; } return nf; } bool bfs(int s, int e) { dist.assign(n, INF); par.assign(n, 0); queue<int> q; q.push(s); dist[s] = 0; while (q.size()) { int u = q.front(); q.pop(); if (u == e) break; for (int idx : adj[u]) { if (el[idx].cap > el[idx].flow && dist[el[idx].v] > dist[el[idx].u] + 1) { dist[el[idx].v] = dist[el[idx].u] + 1; par[el[idx].v] = idx; q.push(el[idx].v); } } } return dist[e] < INF; } int dfs(int s, int e, int f = INT_MAX) { if (s == e || f == 0) return f; for (int idx : adj[s]) { if (dist[el[idx].v] != dist[s] + 1) continue; if (int nf = dfs(el[idx].v, e, min(f, el[idx].cap - el[idx].flow))) { el[idx].flow += nf; el[idx^1].flow -= nf; return nf; } } return 0; } long long dinic(int s, int e) { long long mf = 0; while (bfs(s, e)) { while (int nf = dfs(s, e)) mf += nf; } return mf; } };
Editor is loading...