# Dinic's algorithm

unknown
c_cpp
2 years ago
2.0 kB
3
Indexable
Never
```struct max_flow_graph {
struct edge {
int u, v, cap, flow;
};
int n;
vector<edge> el;
vector<int> dist, par;
max_flow_graph(int n) : n(n), adj(n) {}
void add_edge(int u, int v, int w) {
el.push_back({u, v, w, 0});
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;
}
};```