P3381 【模板】最小费用最大流
大意
求最小费用，最大流。
思路
我们思考这样的问题，我们求最大流的过程中，在增广这一步，最开始我们是随便增广的，这无所谓，只要我们能找到增广路就行，只要找到了增广路，就可以继续进行我们的网络流算法。
那么不妨设想，我们加入了最小花费的代价之后呢？我们要求最小，那么我们在增广的时候，就要选择花费少的，所以我们尝试把增广的过程用 SPFA 代替，这样，我们在增广的时候，利用 EK，每次找出来的链，一定是花费最小的。
代码
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
const int MAX_N = 10000;
const int MAX_M = 100000;
const int inf = 0x3f3f3f3f;
struct edge {int v, c, w, next;
} e[MAX_M];
int p[MAX_N], s, t, eid;
void init() {memset(p, -1, sizeof(p));eid = 0;
}
void insert(int u, int v, int c, int w) {e[eid].v = v;e[eid].c = c;e[eid].w = w;e[eid].next = p[u];p[u] = eid++;
}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w);insert(v, u, 0, -w);
}bool vis[MAX_N];
int d[MAX_N];
int pre[MAX_N];bool spfa(){memset(vis, 0, sizeof(vis));memset(d, 0x3f, sizeof(d));memset(pre, -1, sizeof(pre));d[s] = 0;vis[s] = true;queue<int> q;q.push(s);while(!q.empty()){int u = q.front();q.pop();vis[u] = false;for(int i = p[u];i != -1;i = e[i].next){if(e[i].c){int v = e[i].v;if(d[u] + e[i].w < d[v]){d[v] = d[u] + e[i].w;pre[v] = i;if(!vis[v]){q.push(v);vis[v] = true;}}}}}return pre[t] != -1;
}pair<int,int> costflow(){int ret = 0, res = 0;while(spfa()){int flow = inf;for(int i = t;i != s;i = e[pre[i] ^ 1].v){flow = min(e[pre[i]].c, flow);}for(int i = t;i != s;i = e[pre[i] ^ 1].v){e[pre[i]].c -= flow;e[pre[i] ^ 1].c += flow;ret += e[pre[i]].w * flow;}res += flow;}return {res, ret};
}int main() {int n, m;init();cin >> n >> m >> s >> t;for(int i = 0;i < m;i ++){int u, v, c, w;cin >> u >> v >> c >> w;addedge(u, v, c, w);}pair<int, int> ans = costflow();cout << ans.first << ' ' << ans.second << endl;return 0;
}