洛谷 [P3381] 最小费用最大流模版

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 5005;
int init() {
	int rv = 0, fh = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') fh = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		rv = (rv<<1) + (rv<<3) + c  - '0';
		c = getchar();
	}
	return fh * rv;
}
int head[MAXN], nume, n, m, mincost, maxflow, ss, tt, delta, dis[MAXN], pre[MAXN];
bool f[MAXN];
struct edge{
	int to, nxt, flow, cap, cost;
}e[MAXN * 30];
void adde(int from, int to, int cap, int cost) {
	e[++nume].to = to;
	e[nume].cap = cap;
	e[nume].cost = cost;
	e[nume].nxt = head[from];
	head[from] = nume;
}
queue <int> q;
bool SPFA() {
	memset(dis, 0x3f, sizeof(dis));
	memset(pre, 0, sizeof(pre));
	q.push(ss); dis[ss] = 0; pre[ss] = 0; f[ss] = 1;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		f[u] = 0;
		for(int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if(e[i].flow < e[i].cap && dis[v] > dis[u] + e[i].cost) {
				dis[v] = dis[u] + e[i].cost;
				pre[v] = i;
				if(!f[v]) {
					q.push(v); f[v] = 1;
				}
			}
		}
	}
	return dis[tt] != 0x3f3f3f3f;
}
void MCMF() {
	while(SPFA()) {
		delta = 0x3f3f3f3f;
		for(int i = pre[tt]; i; i = pre[e[(((i - 1) ^ 1) + 1)].to])
			delta = min(delta, e[i].cap - e[i].flow);
		for(int i = pre[tt]; i; i = pre[e[((i - 1) ^ 1) + 1].to]) {
			e[i].flow += delta;
			e[((i - 1) ^ 1) + 1].flow -= delta;
			mincost += delta * e[i].cost;
		}
		maxflow += delta;
	}
}
int main() {
	n = init(); m = init(); ss = init(); tt = init();
	for(int i = 1; i <= m; i++) {
		int u = init(), v = init(), cap = init(), cost = init();
		adde(u, v, cap, cost); adde(v, u, 0, -cost);
	}
	MCMF();
	printf("%d %d
", maxflow, mincost);
	return 0;
}