題目：利用Ford_Fulkerson (標號法)求圖1(a)及2(a)所示的容量網絡的最大流，輸出各條弧及其流量，以及求得的最大流流量。

? (1)

(2)

分析：

?????? 在下面的程序中，以鄰接矩陣存儲容量網絡，但鄰接矩陣中的元素為結構體ArcType類型變量。該結構體描述了網絡中弧的結構，包含容量c和流量f兩個成員。在程序中，還定義了三個數組：flag[n], prev[n], alpha[n]，其中：

1) flag[n]表示頂點狀態，其元素取值及含義為：-1－未標號，0－已標號未檢查，1－已標號已檢查；

2) prev[n]為標號的第一個分量：指明標號從哪個頂點得到，以便找出可改進量；

3) alpha[n]為標號的第二個分量：用以確定增廣路的可改進量α。

?????? 另外，如前所述，從一個已標號未檢查的頂點出發，對它的鄰接頂點進行標號時，采用的是廣度優先搜索的策略，因此，在程序中，定義了一個數組queue[n]來模擬隊列；并定義了兩個相關變量qs和qe，分別表示隊列頭位置和隊列尾位置，約定從隊列頭取出結點，從隊列尾插入結點；當qs<qe時表示隊列非空。

每一次標號過程為：
(1)? 先將flag、prev和alpha這3個數組各元素都初始化-1。

(2)? 將源點初始化為已標號未檢查頂點，即flag[0] = 0, prev[0] = 0, alpha[0] = INF，INF表示無窮大；并將源點入隊列。

(3)? 當隊列非空并且匯點沒有標號，從隊列頭取出隊列頭頂點，設這個頂點為v，v肯定是已標號未檢查頂點；因此，檢查頂點v的正向和反向“鄰接”頂點，如果沒有標號并當前可以進行標號，則對這些頂點進行標號并入隊列，這些頂點都是已標號未檢查頂點；此后頂點v為已標號已檢查頂點。反復執行這一步直至隊列為空或匯點已獲得標號。

?

????? 標號完畢后，要進行調整，調整方法是：從匯點出發，通過標號的第1個分量，即prev[5],采用“倒向追蹤”方法，一直找到源點為止，這個過程途經的頂點和弧就構成了增廣路。可改進量為匯點標號的第2個分量，即alpha[5]。

?

代碼：

#include <iostream> #include <cstring> #include <cmath> #include <cstring>using namespace std;#define MIN(a, b) (a > b ? b : a)const int MAXN = 1000; const int INF = 10000000;struct ArcType//每個弧的容量以及弧的實際流量 {int c, f; };ArcType Edge[MAXN][MAXN];int flag[MAXN];//如果該頂點沒有標號則為-1，如果已經訪問，且沒有檢查其鄰接頂點則標記為0，如果已經訪問并且已經檢查其鄰接頂點則標記為1； int pre[MAXN];//pre[i]表示標號時，頂點i的前一個頂點，即第一個分量 int alpha[MAXN];//標號時第二個分量 int que[MAXN];//廣搜時的隊列int v;//隊列頭元素出隊時，接收隊頭元素； int qs, qe;//qs類似隊列對頭指針，qe為隊尾指針 int i, j; int n, m;//圖的頂點數，邊數void Ford_Fulkerson() {while(1){memset(flag, 0xff, sizeof(flag));memset(alpha, 0xff, sizeof(alpha));memset(pre, 0xff, sizeof(pre));flag[0] = 0;//源點標記已經訪問而未檢查，并且入隊，pre[0] = 0;//一般都是把源點的前一個頂點設置為0，其第二個分量標記為無窮大，因為從源點可以流出任意多的流量alpha[0] = INF;qs = qe = 0;que[qe++] = 0;while(qs < qe && flag[n-1] == -1)//如果匯點未被標記，則進行下去{v = que[qs++];for(i = 0; i < n; ++i)//檢查v的鄰接頂點{if(flag[i] == -1)//頂點i未被訪問{if(Edge[v][i].c < INF && Edge[v][i].f < Edge[v][i].c){pre[i] = v;flag[i] = 0;alpha[i] = MIN(alpha[v], Edge[v][i].c - Edge[v][i].f);que[qe++] = i;}else if( Edge[i][v].c < INF && Edge[i][v].f > 0){pre[i] = -v;flag[i] = 0;alpha[i] = MIN(alpha[v], Edge[i][v].f);que[qe++] = i;}}}flag[v] = 1;//把v標記為已經訪問，并且已經檢查過了}if(flag[n-1] == -1 || alpha[n-1] == 0)//如果匯點不能被標記，或者被標記了但是其第二個分量為0，則表示圖中已經不存在增廣路，已經達到最大流break;int k1 = n-1, k2 = fabs( pre[k1] );//倒向追蹤，如果是正向弧則該弧的實際流量加上匯點的第二分量（即可增加量），如果是反向弧，則反向弧上的實際流量減去匯點的第二個分量int a = alpha[k1];while( 1 ){if(Edge[k2][k1].f < INF)Edge[k2][k1].f = Edge[k2][k1].f + a;elseEdge[k1][k2].f = Edge[k1][k2].f - a;if(k2 == 0)break;k1 = k2, k2 = fabs(pre[k2]);}}int maxflow = 0;for(i = 0; i < n; ++i)//計算最大流，并且輸出各個弧的流量{for(j = 0; j < n; ++j){if(i == 0 && Edge[i][j].f < INF)maxflow += Edge[i][j].f;if(Edge[i][j].f < INF)cout<<i<<" -> "<<j<<":"<<Edge[i][j].f<<endl;}}cout<<"MAXFLOW: "<<maxflow<<endl; }int main() {int u, v, c, f;while(cin>>n>>m)//n是頂點數，m是邊數{if(n == 0 && m == 0)break;for(i = 0; i < n; ++i)for(j = 0; j < n; ++j)Edge[i][j].c = Edge[i][j].f = INF;for(j = 0; j < m ; ++j){cin>>u>>v>>c>>f;Edge[u][v].c = c;Edge[u][v].f = f;}Ford_Fulkerson();}return 0; } /**6 10 0 1 8 2 0 2 4 3 1 3 2 2 1 4 2 2 2 1 4 2 2 3 1 1 2 4 4 0 3 4 6 0 3 5 9 3 4 5 7 2 */

?

總結

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

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