【概述】

在求解費用流時，大多數(shù)情況都是使用基于 SPFA 的 MCMF 算法，但有時某些毒瘤題會卡 SPFA，此時就要利用基于 Dijkstra 的費用流來求解。

【算法原理】

基于 Dijkstra 的費用流實質(zhì)上就是在 MCMF 中代替?SPFA 來找增廣路徑，由于 Dijkstra 只能處理負(fù)邊權(quán)圖，因此在求費用流時，需要對圖進(jìn)行處理，來保證邊權(quán)非負(fù)

引入一個勢能函數(shù) h[x]，Dijkstra 每進(jìn)行松弛操作時，加入勢能函數(shù)來進(jìn)行相應(yīng)的考慮，其引入勢能函數(shù)的過程，本質(zhì)上就是 Johnson 算法對邊重賦值的過程

即對于 u、v?兩點，原來的松弛操作是：dis[u]>dis[v]+w(u,v)

引入勢能函數(shù)后有：dis[u]>dis[v]+w(u,v)+h[u]-h[v]

因此只需要保證 w(u,v)+h[u]-h[v] 是正的，那么整張圖就不存在負(fù)邊權(quán)

下面考慮如何構(gòu)造勢能函數(shù) h[x]：

設(shè) disG?為原圖第 i 次增廣后的 disG 數(shù)組，那么考慮原圖最短路的松弛：對于某一條邊 w(u,v)，有：disG[u]>=disG[u]+w(u,v)，即 disG[u]-disG[v]>=w(u,v)

因此可令勢能函數(shù) h[u]=disG[u]，h[v]=disG[v]，其中 disG[u] 為原圖上一次最短路松弛后的 dis 的值

因此，在每一輪的增廣開始時前，h[i] 必須是上一次增廣的 dis[i]，故每次增廣完成后，h[i] 要加上 dis[i]，這樣 h[i] 就變成了這次增廣的 disG[i]，以供下一次增廣使用。

此外，需要注意的是，基于 Dijkstra 的費用流不能用鏈?zhǔn)角跋蛐莵韺?#xff0c;要用 vector 來寫，而且在 vector 的結(jié)構(gòu)體中，要多一個維度 rev，以尋找反向弧，這樣的好處是在增廣時可以根據(jù) preV、preE 兩個前趨數(shù)組沿匯點回到起點。

【模版】

#define Pair pair<int,int> struct Edge {int to;int cap, dis; //容量、費用int rev; //(u,v)的反向弧中,v在u的位置Edge() {}Edge(int to, int cap, int dis, int rev): to(to), cap(cap), dis(dis), rev(rev) {} }; vector<Edge> G[N]; struct Pre { //記錄前驅(qū)int node; //前驅(qū)結(jié)點int edge; //對應(yīng)的邊 } pre[N]; int h[N]; //勢能函數(shù) int dis[N]; //費用 void addEdge(int x, int y, int cap, int dis) {G[x].push_back(Edge(y, cap, dis, (int)G[y].size())); //正向邊G[y].push_back(Edge(x, 0, -dis, (int)(G[x].size() - 1))); //反向邊 } bool Dijkstra(int S, int T) {memset(dis, INF, sizeof(dis));dis[S] = 0;priority_queue<Pair, vector<Pair>, greater<Pair>> Q;Q.push(Pair(dis[S], S));while (!Q.empty()) {Pair now = Q.top();Q.pop();int u = now.second;if (dis[u] < now.first)continue;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i].to;int cap = G[u][i].cap;int w = G[u][i].dis;if (cap && dis[v] > w + dis[u] + h[u] - h[v]) {dis[v] = w + dis[u] + h[u] - h[v]; //進(jìn)行松弛pre[v].node = u; //記錄前驅(qū)點pre[v].edge = i; //記錄前驅(qū)邊Q.push(Pair(dis[v], v));}}}if (dis[T] == INF)return false;else {for (int i = 0; i <= T + 1; i++) //對于勢能函數(shù)，每次加上當(dāng)前輪的dish[i] += dis[i];return true;} } void maxFlow(int S, int T, int &flow, int &cost) {memset(h, 0, sizeof(h));memset(pre, 0, sizeof(pre));int newFlow = 0; //增廣流量while (flow && Dijkstra(S, T)) { //當(dāng)無法增廣時，即找到答案int minn = INF;for (int i = T; i != S; i = pre[i].node) {int node = pre[i].node;int edge = pre[i].edge;minn = min(minn, G[node][edge].cap);}flow -= minn; //原流量newFlow += minn; //增廣流量cost += h[T] * minn; //增廣流花銷for (int i = T; i != S; i = pre[i].node) {int node = pre[i].node;int edge = pre[i].edge;int rev = G[node][edge].rev;G[node][edge].cap -= minn;G[i][rev].cap += minn;}} } int main() {int n, m;scanf("%d%d", &n, &m);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;int flow = INF;//最大流量，根據(jù)題目設(shè)置int cost = 0;maxFlow(S, T, flow, cost);printf("%d\n", cost);return 0; }

?

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。