网络最大流（模板）

不加弧优化

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10005;
int n, m, s, t;
struct edge {int v, nxt, val;} e[N * 2];
int head[N], cnt = 1;
int dis[N];
int maxflow;
void add(int u, int v, int val) {
	e[++cnt].val=val;
	e[cnt].v=v;
	e[cnt].nxt=head[u];
	head[u] = cnt;
	
	e[++cnt].val=0;
	e[cnt].v=u;
	e[cnt].nxt=head[v];
	head[v] = cnt;
}
bool bfs() {
	queue<int>q;
	memset(dis, -1, sizeof(dis));
	q.push(s);
	dis[s] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = head[x]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (dis[v] == -1 && e[i].val) {
				q.push(v);
				dis[v] = dis[x] + 1;
			}
		}
	}
	return dis[t] != -1;
}
int dfs(int u, int flow) {
	if (u == t) return flow;
	int res = 0;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (dis[v] == dis[u] + 1 && e[i].val) {
			int fl = dfs(v, min(e[i].val, flow));
			if (fl) {
				e[i].val -= fl;
				e[i ^ 1].val += fl;
				flow -= fl;
				res += fl;
				if (!flow) return res;
			}
		}
	}
	return res;
}
signed main() {
	scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
	for (int i = 1; i <= m; ++i) {
		int x, y, val;
		scanf("%lld%lld%lld", &x, &y, &val);
		add(x, y, val);
	}
	while (bfs()) maxflow += dfs(s, 1 << 29);
	cout << maxflow;
	return 0;
}

加弧优化

  #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10005;
int n, m, s, t;
struct edge {int v, nxt, val;} e[N * 2];
int head[N], cnt = 1;
int dis[N];
int cur[N];//弧优化数组
int maxflow;
void add(int u, int v, int val) {
	e[++cnt].val=val;
	e[cnt].v=v;
	e[cnt].nxt=head[u];
	head[u] = cnt;
	
	e[++cnt].val=0;
	e[cnt].v=u;
	e[cnt].nxt=head[v];
	head[v] = cnt;
}
bool bfs() {
	queue<int>q;
	for(int i=1;i<=n;i++){
		dis[i]=-1;
		cur[i]=head[i];
	}
	q.push(s);
	dis[s] = 1;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = head[x]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (dis[v] == -1 && e[i].val) {
				q.push(v);
				dis[v] = dis[x] + 1;
			}
		}
	}
	return dis[t] != -1;
}
int dfs(int u, int flow) {
	if (u == t) return flow;
	int res = 0;
	for (int i = cur[u]; i; i = e[i].nxt) {
		cur[u]=i;
		int v = e[i].v;
		if (dis[v] == dis[u] + 1 && e[i].val) {
			int fl = dfs(v, min(e[i].val, flow));
			if (fl) {
				e[i].val -= fl;
				e[i ^ 1].val += fl;
				flow -= fl;
				res += fl;
				if (!flow) return res;
			}
		}
	}
	return res;
}
signed main() {
	scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
	for (int i = 1; i <= m; ++i) {
		int x, y, val;
		scanf("%lld%lld%lld", &x, &y, &val);
		add(x, y, val);
	}
	while (bfs()) maxflow += dfs(s, 1 << 29);
	cout << maxflow;
	return 0;
}