活動 - AcWing
給定一個包含?n?個點?m?條邊的有向圖，并給定每條邊的容量和費用，邊的容量非負。
圖中可能存在重邊和自環，保證費用不會存在負環。
求從?S?到?T?的最大流，以及在流量最大時的最小費用。
輸入格式
第一行包含四個整數?n,m,S,T。
接下來?m?行，每行三個整數?u,v,c,w，表示從點?u?到點?v?存在一條有向邊，容量為?c，費用為?w。
點的編號從?1?到?n。
輸出格式
輸出點?S?到點?T?的最大流和流量最大時的最小費用。
如果從點?S?無法到達點?T?則輸出?0 。
數據范圍
2≤n≤5000,
1≤m≤50000,
0≤c≤100,
?100≤w≤100
S≠T
輸入樣例：
5 5 1 5
1 4 10 5
4 5 5 10
4 2 12 5
2 5 10 15
1 5 10 10
輸出樣例：
20 300解析：?
對于 n?個節點，m?條邊的流網絡，可以在 O(nm^2)?的時間復雜度內求出該流網絡的 最小費用最大流（最大費用最大流）。
算法步驟：
用 while 循環不斷判斷殘量網絡中是否存在增廣路徑。
對于循環中：
1.找到增廣路徑
2.更新殘量網絡
3.累加最大流量
4.循環結束，得出最大流。
注意： EK 算法原本是用于求最大流的，但是經過嚴格的證明之后，只需要將 EK 算法中找增廣路徑的 bfs 算法替換成 spfa 算法即可。如果要求最小費用最大流，就用 spfa 算法找最短增廣路；如果要求最大費用最大流，就用 spfa 算法找最長增廣路。（注意：由于是使用spfa求最短路，所以費用不能有負環）
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 5e3 + 10, M = (5e4) * 2 + 10, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], dist[N], incf[N],pre[N];
bool st[N];void add(int a, int b, int c, int d) {e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}bool spfa() {int hh = 0, tt = 1;memset(dist, 0x3f, sizeof dist);memset(incf, 0, sizeof incf);q[0] = S, dist[S] = 0, incf[S] = INF;while (hh != tt) {int t = q[hh++];if (hh == N)hh = 0;st[t] = 0;for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (f[i] && dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];incf[j] = min(incf[t], f[i]);pre[j] = i;if (!st[j]) {st[j] = 1;q[tt++] = j;if (tt == N)tt = 0;}}}}return incf[T] > 0;
}void EK(int& flow, int& cost) {flow = cost = 0;while (spfa()) {int t = incf[T];flow += t, cost += t * dist[T];for (int i = T; i != S; i = e[pre[i] ^ 1]) {f[pre[i]] -= t;f[pre[i] ^ 1] += t;}}
}int main() {cin >> n >> m >> S >> T;memset(h, -1, sizeof h);for (int i = 1,a,b,c,d; i <= m; i++) {scanf("%d%d%d%d", &a, &b, &c, &d);add(a, b, c, d);}int flow, cost;EK(flow, cost);cout << flow << " " << cost << endl;return 0;
}
