洛谷 [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;
}