算法模板（8）：网络流（3）：费用流

• 题意：给定一个包含 $n$ 个点 $m$ 条边的有向图，并给定每条边的容量和费用，边的容量非负。图中可能存在重边和自环，保证费用不会存在负环。求从 $S$ 到 $T$ 的最大流，以及在流量最大时的最小费用。
• 每次沿着最短路增广，得到的费用是最小的。然后就是把 $EK$ 算法中的 $bfs$ 换成最短路即可，最短路中间加上对流量的更新即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 5010, M = 100010, INF = 1e8;
int h[N], e[M], ne[M], f[M], w[M], idx;void add(int a, int b, int c, int d)
{e[idx] = b, ne[idx] = h[a], f[idx] = c, w[idx] = d, h[a] = idx++;e[idx] = a, ne[idx] = h[b], f[idx] = 0, w[idx] = -d, h[b] = idx++;
}
int n, m, S, T;
int incf[N], d[N], pre[N];
bool st[N];bool spfa()
{memset(d, 0x3f, sizeof d);memset(incf, 0, sizeof incf);queue<int> que;d[S] = 0, incf[S] = INF;que.push(S);while(que.size()){int u = que.front(); que.pop();st[u] = false;for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(f[i] && d[v] > d[u] + w[i]){d[v] = d[u] + w[i];pre[v] = i;incf[v] = min(f[i], incf[u]);if(!st[v]){que.push(v);st[v] = true;}}}}return incf[T] > 0;
}void EK(int& flow, int& res)
{flow = 0, res = 0;while(spfa()){int t = incf[T];flow += t, res += t * d[T];for(int i = T; i != S; i = e[pre[i] ^ 1]){f[pre[i]] -= t, f[pre[i] ^ 1] += t;}}
}int main()
{memset(h, -1, sizeof h);scanf("%d%d%d%d", &n, &m, &S, &T);for(int i = 1; i <= m; i++){int a, b, c, d;scanf("%d%d%d%d", &a, &b, &c, &d);add(a, b, c, d);}int flow, res;EK(flow, res);printf("%d %d\n", flow, res);return 0;
}s