最小費用最大流

1.解決的問題

最大流可以以多種方式到達，求解費用最小的最大流。

2.預備知識

(1)Dijkstra算法可以很好地解決無負權邊的最短路徑問題，而不能解決含有負權邊的問題。若當前距離源點最短的點為A，長度為a,了經過其他點B到達A的的路徑為b+ab(b為源點到B的距離，ab為邊AB的長度)，因為a<b，而ab為正數，則必有a<a+ab，因此認為經過其余點到達A的距離一定大于從源點到A的距離，因此認定A的最短路已經找到。若ab小于0，則上述不等式不一定成立，因此Dijkstra算法不一定成立，此時，可以使用spfa來進行解決。
(2)SPFA算法的時間復雜度為O(VE)。主要思想是，設立一個先進先出的隊列來保存待優化的節點，當節點u出隊時，用其當前的最短距離來更新與其鄰接的點v的最短距，若v的最短距離發生了變化，則將v加入隊列中。如此一直重復下去，直到隊列為空。（每一個點的松弛次數不能大于總的點數，否則出現負權環）SPFA算法能夠處理負權邊的本質在于，將最短路徑的找到等同于隊列為空，即一個點可以被松弛多次。

負權環導致問題的原因:
環中某點更新后變小，將其傳遞給下一個點，由于下一個點本就是由該點更新的，因此下一個點也會更新變小，依此傳遞下去，若為負權環，則起始點比初始值更小，導致下一輪傳播，若非負權環，則不會更新。

(3)在網絡流問題中，由于添加了反向邊，因此無論增廣的順序如何，最終都能找到最大流。基于此，可以每次去找一條費用最小的增廣路徑進行流量的增加。

3.解決思路

1.以單價為邊建立圖G
2.使用sfpa求出從源點到匯點的最短路，若找不到，則算法結束；若找到，并找出路徑上的最大流量f
3.更新該路徑上的殘余流量，若等于0，則在圖G中刪除這條邊，轉2

注意:反向邊的cap為0（使得剩余流量為正數）。且由于反向邊是為了反悔用的，因此cost為負數。

4.例題 poj2135

#include<iostream> #include<vector> #include<queue> using namespace std; #define NMAX 1100 #define INF 0x3f3f3f3f struct edge {int from, to, cap, flow, cost; }; vector<edge> E; vector<int> G[NMAX];//記錄的是起點為i的所有的邊 //題目當中的變量 int N, M; //N代表的是不包括源點和匯點的總共點數 //Mincost需要使用的變量 int inq[NMAX] = { 0 };//代表是否在隊列中 int dis[NMAX];//代表的是源點到點的距離 int cflow[NMAX]; //代表當前路徑上的最小流量 int pre[NMAX] = { 0 };//代表導向該點的上一條弧 void AddEdge(int from ,int to, int cap, int cost) {struct edge ce;ce.from = from, ce.to = to, ce.cap = cap, ce.flow = 0, ce.cost = cost;E.push_back(ce);ce.from = to, ce.to = from, ce.cap = 0, ce.flow = 0, ce.cost = -cost;E.push_back(ce);//反向邊的容量為0，價格為負數int m = E.size();G[from].push_back(m - 2);G[to].push_back(m - 1); }int SPFA(int s, int d, int& cost, int& flow) {for (int i = 1; i <= N + 2; i++) dis[i] = INF, cflow[i] = INF, inq[i] = 0;queue<int> Q;//存放點Q.push(s);inq[s] = 1;//代表源點已經放入隊列中dis[s] = 0;//源點的距離一定要初始化為0while (!Q.empty()) {int cs = Q.front();Q.pop();inq[cs] = 0;//cs出隊列for (int i = 0; i < G[cs].size(); i++) {int num = G[cs][i];int cd = E[num].to; //判斷條件先看這條邊是否還有流量if ((E[num].cap - E[num].flow) > 0) {if (dis[cd] > E[num].cost + dis[cs] ) {//更新最短距離dis[cd] = E[num].cost + dis[cs];//更新路徑上的最小流量cflow[cd] = min(cflow[cs], E[num].cap - E[num].flow);//更新鏈接關系pre[cd] = num;//如果沒有在隊列中，則將其加入隊列以方便對于其他元素進行更新if (!inq[cd]) {Q.push(cd);inq[cd] = 1;}}}}}if (dis[d] == INF) return 0;//更新流量和成本flow += cflow[d];cost += dis[d] * cflow[d];//利用pre更新圖,注意首先應該從點出發//需要注意的是，這里是雙向圖int cur = d;while (cur != s) {int num = pre[cur];E[num].flow += cflow[d];E[num ^ 1].flow -= cflow[d]; //num ^ 1代表的是相反的那條邊的編號cur = E[num].from;}return 1; } int Mincost(int s, int d) {int cost = 0, flow = 0;while (SPFA(s, d, cost, flow));return cost; }int main() {cin >> N >> M;for (int i = 0; i < M; i++) {int s, d, l;cin >> s >> d >> l;AddEdge(s, d, 1, l);AddEdge(d, s, 1, l);//無向圖注意反向邊的添加}AddEdge(N + 1, 1, 2, 0);AddEdge(N, N + 2, 2, 0);cout << Mincost(N + 1, N + 2); }

參考鏈接:
SPFA判斷負權環
最小費用最大流

總結

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

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