【概述】

求解費用流的方法很多，目前最流行的是 MCMF 費用流，其實質是將 EK 算法中的 bfs 換為了 SPFA 來計算最小費用，但其存在的一個缺點是 EK 是單路增廣的，這樣速度會相應的慢一些

然后 zkw 神犇進行了改進，在 dfs 的時候實現多路增廣，利用 KM 算法來代替 SPFA 算法來修改頂標，簡單來說，其將 EK 費用流與 Dinic 費用流結合了起來。

【算法原理】

回憶一下 Dinic 算法找增廣路的過程，該算法一遇到一條可以走的邊就走，直到走出來一條源點到匯點的一條可行的路徑

再回憶一下 EK 費用流（MCMF 費用流）的過程，先跑一遍 SPFA，使其找出一條流量不為 0 的具有最小費用的從源點到匯點的路徑，然后每次做 SPFA 增廣一條路徑

對于 MCMF 來說，每次做 SPFA 只能增廣一條路徑，這無疑是極大的浪費

對于當前增廣的路徑來說，由于一條不在最短路圖上的路徑的費用肯定沒有最短路圖上的費用小，因此其肯定在源點的最短路圖上，那么這個最短路圖是可以一次 SPFA 跑出來的

這時，順著最短路圖做一次 Dinic 找增廣路即可，此外，在做 SPFA 時，可以順便進行分層，從而可以很好的利用 Dinic 的分層優化，SPFA 的 SLF 優化也可以加上

原版的 zkw 費用流沒有利用 SPFA 算法，利用了 KM 算法來修改頂標，但這樣無法處理具有負邊權的情況，利用 SPFA 的 zkw 費用流的改進版則沒有這種缺陷。

zkw 費用流的優點大于缺點，在數據量較大特別是增廣路較多、較長的時候，優勢十分明顯，而當數據量較小時，常數十分大

原版的 zkw 費用流：點擊這里

【源代碼】

struct Edge {int to;int next;int cap, cost; } edge[N]; int head[N], tot; bool vis[N]; int dis[N], level[N];void addEdge(int x, int y, int cap, int cost) {edge[++tot].to = y;edge[tot].next = head[x];edge[tot].cap = cap;edge[tot].cost = cost;head[x] = tot;edge[++tot].to = x;edge[tot].next = head[y];edge[tot].cap = 0;edge[tot].cost = -cost;head[y] = tot; }bool SPFA(int S, int T, int n) {memset(dis, INF, sizeof(dis));memset(vis, false, sizeof(vis));memset(level, 0, sizeof(level));dis[S] = 0;level[S] = 1;vis[S] = true;deque<int> Q;Q.push_back(S);while (!Q.empty()) {int x = Q.front();Q.pop_front();vis[x] = false;for (int i = head[x]; i != -1; i = edge[i].next) {int to = edge[i].to;if (dis[to] > dis[x] + edge[i].cost && edge[i].cap > 0) {dis[to] = dis[x] + edge[i].cost;level[to] = level[x] + 1;if (!vis[to]) {vis[to] = true;if (!Q.empty() && dis[to] < dis[Q.front()])Q.push_front(to);elseQ.push_back(to);}}}}return dis[T] != dis[n + 1]; }bool flag = false; int dfs(int x, int T, int t, int &flow, int &cost) {if (x == T) {flow += t;flag = true;return t;}int num = 0, newFlow = 0;for (int i = head[x]; i != -1; i = edge[i].next) {int to = edge[i].to;if (t == num)break;if (dis[x] + edge[i].cost == dis[to] && level[x] + 1 == level[to] && edge[i].cap > 0) {newFlow = dfs(to, T, min(t - num, edge[i].cap), flow, cost);num += newFlow;cost += newFlow * edge[i].cost;edge[i].cap -= newFlow;edge[i ^ 1].cap += newFlow;}}return num; } void zkw(int S, int T, int n) {int flow = 0, cost = 0;while (SPFA(S, T, n)) {flag = true;while (flag) {flag = false;dfs(S, T, INF, flow, cost);}}printf("%d %d\n", flow, cost); }int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {memset(head, -1, sizeof(head));tot = 1;for (int i = 1; i <= m; i++) {int x, y, cap, cost;scanf("%d%d%d%d", &x, &y, &cap, &cost);addEdge(x, y, cap, cost);}int S=1,T=n;zkw(S, T, n);}return 0; }

?

總結

以上是生活随笔為你收集整理的图论 —— 网络流 —— 费用流 —— zkw 费用流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。