洛谷 [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\n", maxflow, mincost);

	return 0;

}