网络流模板

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int n, m, s, t, tot = 1, dep[10005], head[10005], to[200005], nxt[200005], w[200005], cu[10005];

queue < int > q;

ll res;

int read()
{
	int x = 0, fl = 1; char ch = getchar();
	while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) fl = -1; ch = getchar();}
	while (ch >= ‘0‘ && ch <= ‘9‘) {x = (x << 1) + (x << 3) + ch - ‘0‘; ch = getchar();}
	return x * fl;
}

void add(int x, int y, int z)
{
	tot ++ ;
	w[tot] = z;
	nxt[tot] = head[x];
	to[tot] = y;
	head[x] = tot;
	return;
}

int bfs()
{
	for (int i = 1; i <= n; i ++ ) cu[i] = head[i]; // 注意1
	dep[s] = 1; q.push(s);
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		for (int i = head[x]; i; i = nxt[i])
		{
			int y = to[i], z = w[i];
			if (z && (!dep[y]))
			{
				dep[y] = dep[x] + 1;
				q.push(y);
			}
		}
	}
	return dep[t];
}

ll dinic(int cur, ll flow)
{
	if (cur == t) return flow;
	for (int &i = cu[cur]; i; i = nxt[i]) // 注意2
	{
		int y = to[i], z = w[i];
		if (z && (dep[y] == dep[cur] + 1))
		{
			ll d = dinic(y, min(flow, (ll)z));
			w[i] -= d; w[i ^ 1] += d;
			if (d) return d;
		}
	}
	return 0;
}

int main()
{
	n = read(), m = read(), s = read(), t = read();
	for (int i = 1; i <= m; i ++ )
	{
		int u = read(), v = read(), w = read();
		add(u, v, w); add(v, u, 0);
	}
	while (bfs())
	{
		while (ll ans = dinic(s, 2e9)) res += ans;
		memset(dep, 0, sizeof(dep)); // 多路增广
	}
	printf("%lld\n", res);
	return 0;
}

网络流模板

原文：https://www.cnblogs.com/andysj/p/14546197.html