网络流-最大流问题

Dear 丶 2022-05-28 08:11 157阅读 0赞

限制:管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。

最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。求最大流的标号算法最早由福特和福克逊与与1956年提出，20世纪50年代福特(Ford)、(Fulkerson)建立的“网络流理论”，是网络应用的重要组成成分。  
最大流问题，是网络流理论研究的一个基本问题，求网络中一个可行流f\*，使其流量v(f)达到最大， 这种流f称为最大流，这个问题称为(网络)最大流问题。

算法1:Ford-Fulkerson算法

这个算法非常简单，在此之前，首先我们来思考如何求这个问题！

[HDU 3549][]

![Center][]

对于一个有向图来说，我们求它的最大流，可以dfs从s找一条到e的路嘛，流量就是这条路上的权值最小值嘛！！！然后在这条路上减去流量嘛，然后重复操作咯，只到不能找到路了，嘿嘿哇好简单咯。

但是正确吗？

起码有一点不能保证，怎么保证我们走的这条路，最优解也一定走了？

所以科学家们干了一件大事，每一次对与走过路，用过的流量，我们建立一条反向边（用着后悔，最大流量就是用过的流量），万一下一个dfs找到了更优解了？此处怎么理解了？我们已经建立了反向边，下一个dfs只要用了这些反向边，那么我们就相当于把原来的（正向边的流量减少）逼到这条路上面。

这样dfs下来肯定最优了，每一次都有后悔的反向边，下一次一旦找到更好的马上把原来的流量分给其他路咯！

时间复杂度:记最大流为F，那么算法最多进行F次dfs，O(F\*|E|)

代码如下:

vector存储图

#include<bits/stdc++.h>
    using namespace std;
    
    const int inf=0x3f3f3f3f;
    const int maxn=20;
    struct ege//终点，最大流量，确定反向边的位置
    {
        int to,cap,rev;
    };
    vector<ege> G[maxn];
    bool vis[maxn];
    int n,m;
    
    int dfs(int S,int E,int f)
    {
        if (S==E) return f;
        for (int i=0;i<G[S].size();i++) {
            ege& e=G[S][i];
            if (vis[e.to]==false&&e.cap>0) {
                vis[e.to]=true;
                int d=dfs(e.to,E,min(f,e.cap));
                if (d>0) {
                    e.cap-=d;
                    G[e.to][e.rev].cap+=d;//反向边来加流量，保证可以反悔
                    return d;
                }
            }
        }
        return 0;
    }
    int max_flow(int s,int e)
    {
        int flow=0;
        while (true) {
            memset (vis,false,sizeof (vis));
            int f=dfs(s,e,inf);
            if (f==0) return flow;//找不到了
            flow+=f;
        }
        return 0;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        for (int icase=1;icase<=t;icase++) {
            scanf("%d%d",&n,&m);
            for (int i=1;i<=n;i++) G[i].clear();
            for (int i=1;i<=m;i++) {
                int s,e, val;
                scanf("%d%d%d",&s,&e,&val);
                G[s].push_back(ege{e,val,G[e].size()});
                G[e].push_back(ege{s,0,G[s].size()-1});
            }
            printf("Case %d: %d\n",icase,max_flow(1,n));
        }
        return 0;
    }

普通二维数组存储图

TLE

#include<bits/stdc++.h>
    using namespace std;
    
    const int inf=0x3f3f3f3f;
    const int maxn=20;
    int G[maxn][maxn];
    bool vis[maxn];
    int n,m;
    
    int dfs(int s,int e,int f)
    {
        if (s==e) return f;
        for (int i=1;i<=n;i++) {
            if (vis[i]==false&&G[s][i]>0) {
                vis[i]=true;
                int d=dfs(i,e,min(f,G[s][i]));
                if (d>0) {
                    G[s][i]-=d;
                    G[i][s]+=d;//反向边来加流量，保证可以反悔
                    return d;
                }
            }
        }
    }
    int max_flow(int s,int e)
    {
        int flow=0;
        while (true) {
            memset (vis,false,sizeof (vis));
            int f=dfs(s,e,inf);
            if (f==0) return flow;//找不到了
            flow+=f;
        }
        return 0;
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        for (int icase=1;icase<=t;icase++) {
            scanf("%d%d",&n,&m);
            memset (G,0,sizeof (G));
            for (int i=1;i<=m;i++) {
                int s,e,flow;
                scanf("%d%d%d",&s,&e,&flow);
                G[s][e]=G[e][s]=flow;
            }
            printf("Case %d: %d\n",icase,max_flow(1,n));
        }
        return 0;
    }

[HDU 3549]: http://acm.hdu.edu.cn/showproblem.php?pid=3549
[Center]: /images/20220528/7f1a6807cd4b467e8c81da5d5dc69498.png