程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 網絡流之一般增廣路算法標號法實現

網絡流之一般增廣路算法標號法實現

編輯：C++入門知識

網絡流之一般增廣路算法標號法實現

數據輸入格式：首先輸入頂點個數n和弧數m，然後輸入每條弧的數據。規定源點為頂點0，匯點為頂點n-1.每條弧的數據格式為：u，v，c，f，分別表示這條弧的起點，終點，容量和流量。頂點序號從0開始。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 1000
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

struct ArcType//弧結構
{
    int c,f;//容量，流量
};

ArcType Edge[MAXN][MAXN];//鄰接矩陣（每個元素為ArcType類型）
int n,m;  //頂點的個數和弧數
int flag[MAXN];  //頂點狀態：-1——未標號，0——已標號未檢查，1——已標號已檢查
int prev[MAXN];  //標號的第一個分量：指明標號是從哪裡得到的，以便找到可改盡量
int alpha[MAXN];  //標號的第二個分量：可改進量
int que[MAXN];  //隊列
int v;  //從隊列中取出來的隊列頭元素
int qs,qe; //隊列頭位置，隊列尾位置
int i,j;  //循環變量

void ford()
{
    while (1)  //標號直到不存在可改進路
    {
        //標號前對頂點狀態數組初始化為-1
        memset(flag,-1,sizeof(flag));
        memset(prev,-1,sizeof(prev));
        memset(alpha,-1,sizeof(alpha));
        flag[0]=0;  prev[0]=0;  alpha[0]=INF;  //源點為已標號未檢查點
        qs=qe=0;
        que[qe]=0;//源點入隊
        qe++;  //qs0)
                    {
                        flag[i]=0; prev[i]=-v;  //給頂點i標號（已標號未檢查）
                        alpha[i]=min(alpha[v],Edge[i][v].f);
                        que[qe]=i;  //頂點i入隊
                        qe++;
                    }
                }
            }
            flag[v]=1;
        }  //end of while (qs%d:%d\n",i,j,Edge[i][j].f);
        }
    }
    printf("maxFlow:%d\n",maxFlow);
}

int main()
{
    int u,v,c,f;  //弧的起點，終點，容量，流量
    while (scanf("%d%d",&n,&m)!=EOF)  //讀入頂點個數n和弧數m
    {
        for (i=0;i