网络流、费用流模板

#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()
{
        memset(dep, 0, sizeof(dep));
	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; // 多路增广
	printf("%lld
", res);
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, m, s, t, tot = 1, mxf, mnc, cost[5005], vis[5005], pre[5005], lst[5005], mf[5005], nxt[100005], head[5005], to[100005], f[100005], c[100005];

queue <int> q;

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

int SPFA()
{
	memset(cost, 0x3f, sizeof(cost));
	memset(mf, 0x3f, sizeof(mf));
	memset(vis, 0, sizeof(vis));
	while (!q.empty()) q.pop();
	vis[s] = 1; cost[s] = 0; q.push(s);
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		vis[x] = 0;
		for (int i = head[x]; i; i = nxt[i])
		{
			int y = to[i], z = c[i];
			if ((f[i] > 0) && (cost[y] > cost[x] + z))
			{
				cost[y] = cost[x] + z;
				pre[y] = x;
				lst[y] = i;
				mf[y] = min(mf[x], f[i]);
				if (!vis[y])
				{
					vis[y] = 1;
					q.push(y);
				}
			}
		}
	}
	return cost[t] != 0x3f3f3f3f;
}

int main()
{
	scanf("%d %d %d %d", &n, &m, &s, &t);
	for (int i = 1; i <= m; i ++ )
	{
		int x, y, z, co;
		scanf("%d %d %d %d", &x, &y, &z, &co);
		add(x, y, z, co); add(y, x, 0, -co);
	}
	while (SPFA())
	{
		int tt = t;
		mxf += mf[t];
		mnc += mf[t] * cost[t];
		while (tt)
		{
			f[lst[tt]] -= mf[t];
			f[lst[tt] ^ 1] += mf[t];
			tt = pre[tt];
		}
	}
	printf("%d %d
", mxf, mnc);
	return 0;
}