网络流模板

using ll = long long;const int MAXN = 100005, MAXM = 100005;
const ll INF = ll(1e18);struct Network {struct Edge {int v, nxt, cap, flow;}e[2 * MAXM];int n, S, T, head[MAXN], tot = -1, dep[MAXN], cur[MAXN];ll maxflow = 0;void init(int n) {fill(head + 1, head + n + 1, -1), tot = 0;}void addedge(int u, int v, int w) {e[++tot] = {v, head[u], w, 0}, head[u] = tot;e[++tot] = {u, head[v], 0, 0}, head[v] = tot;}bool bfs() {queue<int> que;fill(dep + 1, dep + n + 1, 0);dep[S] = 1;que.push(S);while(!que.empty()) {int u = que.front();que.pop();for(int i = head[u]; ~i; i = e[i].nxt) {int v = e[i].v;if(!dep[v] && e[i].cap > e[i].flow) {dep[v] = dep[u] + 1;que.push(v);}}}return dep[T];}int dfs(int u, int flow) {if(u == T || !flow) {return flow;}int ret = 0;for(int &i = cur[u]; ~i; i = e[i].nxt) {int v = e[i].v, d;if(dep[v] == dep[u] + 1 && (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow)))) {ret += d, e[i].flow += d, e[i ^ 1].flow -= d;if(ret == flow) {return ret;}}}return ret;}void dinic() {while(bfs()) {for(int i = 1; i <= n; ++i) {cur[i] = head[i];}maxflow += dfs(S, INF);}}
}G;