Ford-Fulkerson 标号法求网络最大流

墨蓝 2022-09-25 05:20 144阅读 0赞

使用Ford-Fulkerson 标号法求网络最大流。

![20160813212859299][]

## ①c、f初始化为INF表示该边不存在 ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <iomanip>
    #include <algorithm>
    #define maxn 10010
    #define INF 0xfffffff
    using namespace std;
    struct ArcType
    {
        int c,f;//容量、流量
    };
    ArcType edge[maxn][maxn];
    int n,m;//顶点数、弧数
    int flag[maxn];//顶点状态：-1——未标号；0——已标号未检查；1——已标号已检查
    int prev[maxn];//标号的第一个分量：指明标号从哪个顶点而来，以便找出可改进量
    int alpha[maxn];//标号的第二个分量：可改进量α
    int que[maxn];//相当于BFS中的队列
    int v;//队列头元素
    int qs,qe;//队首队尾的位置
    int i,j;
    void ford()//标号法求网络最大流
    {
        while(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;//源点0入队列
            ++qe;
            while(qs<qe&&flag[n-1]==-1)
            {
                v=que[qs];//取队首元素
                ++qs;
                for(i=0; i<n; ++i)//检查顶点v的正向和反向邻接点
                    if(flag[i]==-1)
                    {
                        if(edge[v][i].c<INF&&edge[v][i].f<edge[v][i].c)//正向且未满
                        {
                            flag[i]=0;//给顶点i标号，但此时未检查
                            prev[i]=v;
                            alpha[i]=min(alpha[v],edge[v][i].c-edge[v][i].f);
                            que[qe]=i;//顶点i入队
                            ++qe;
                        }
                        else if(edge[i][v].c<INF&&edge[i][v].f>0)//反向且有流量
                        {
                            flag[i]=0;
                            prev[i]=-v;
                            alpha[i]=min(alpha[v],edge[i][v].f);
                            que[qe]=i;
                            ++qe;
                        }
                    }
                flag[v]=1;//标记顶点i已经检查
            }
            if(flag[n-1]==-1||alpha[n-1]==0) break;//汇点无标号或汇点的调整量为0
            int k1=n-1,k2=abs(prev[k1]);
            int a=alpha[n-1];//可改进量α
            while(1)
            {
                if(edge[k2][k1].f<INF) edge[k2][k1].f+=a;//正向
                else edge[k1][k2].f-=a;//反向
                if(k2==0) break;//一直调整到源点0
                k1=k2;
                k2=abs(prev[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;//弧的起点终点容量流量
        cin>>n>>m;//顶点个数、弧数
        for(i=0; i<n; ++i)
            for(j=0; j<n; ++j)
                edge[i][j].c=edge[i][j].f=INF;//初始化，INF表示无边相连
        for(i=0; i<m; ++i)
        {
            cin>>u>>v>>c>>f;
            edge[u][v].c=c;//构造邻接矩阵
            edge[u][v].f=f;
        }
        ford();
        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
    */

## ②未初始化 ##

void ford()//标号法求网络最大流
    {
        int flow[maxn][maxn];//节点之间的流量Fij
        int prev[maxn];//可改进路径上前一个节点的标号，相当于标号的第一个分量
        int minflow[maxn];//每个顶点的可改进量α，相当于标号的第二个分量
        int que[maxn];
        int qs,qe;//队列首尾位置坐标
        int v,p;//当前顶点、保存Cij-Fij
        for(i=0; i<maxn; ++i)
            for(j=0; j<maxn; ++j)
                flow[i][j]=0;
        minflow[0]=INF;//源点标号的第二分量为无穷大
        while(1)//标号法
        {
            for(i=0; i<maxn; ++i)//每次标号前，每个顶点重新回到未标号状态
                prev[i]=-2;
            prev[0]=-1;
            qs=0;
            que[qs]=0;//源点入队
            qe=1;
            while(qs<qe&&prev[t]==-2)
            {
                v=que[qs];//取队列头节点
                ++qs;
                for(i=0; i<t+1; ++i)//prev[i]==-2表示顶点i未标号
                    if(prev[i]==-2&&(p=edge[v][i].c-flow[v][i]))//edge[v][i].c-flow[v][i]!=0能保证i是v邻接顶点且能进行标号
                    {
                        prev[i]=v;
                        que[qe]=i;
                        ++qe;
                        minflow[i]=(minflow[v]<p)?minflow[v]:p;
                    }
            }
            if(prev[t]==-2) break;//汇点t无标号，标号法结束
            for(i=prev[t],j=t; i!=-1; j=i,i=prev[i])//调整过程
            {
                flow[i][j]+=minflow[t];
                flow[j][i]=-flow[i][j];
            }
        }
        for(i=0,p=0; i<t; ++i)//统计进入汇点的流量即最大流的流量
            p+=flow[i][t];
        cout<<p<<endl;
    }

[20160813212859299]: /images/20220718/3fafe96846b54dd39aa7899b7881d9a1.png