[洛谷P3376题解]网络流（最大流）的实现算法讲解与代码

时间：2023-01-06 06:12:43

[洛谷P3376题解]网络流（最大流）的实现算法讲解与代码

更坏的阅读体验

定义

对于给定的一个网络，有向图中每个的边权表示可以通过的最大流量。假设出发点S水流无限大，求水流到终点T后的最大流量。

起点我们一般称为源点，终点一般称为汇点

内容前置

1.增广路

​ 在一个网络从源点S到汇点T的一条各边剩余流量都大于0(还能让水流通过,没有堵住)的一条路。

2.分层

​ 预处理出源点到每个点的距离(每次寻找增广路都要,因为以前原本能走的路可能因为水灌满了,导致不能走了).作用是保证只往更远的地方放水,避免兜圈子或者是没事就走回头路(正所谓人往高处走水往低处流).

3.当前弧优化

​ 每次增广一条路后可以看做“榨干”了这条路，既然榨干了就没有再增广的可能了。但如果每次都扫描这些“枯萎的”边是很浪费时间的。那我们就记录一下“榨取”到那条边了，然后下一次直接从这条边开始增广，就可以节省大量的时间。这就是当前弧优化

具体怎么实现呢，先把链式前向星的head数组复制一份，存进cur数组，然后在cur数组中每次记录“榨取”到哪条边了。

[#3 引用自](Dinic当前弧优化 模板及教程 - Floatiy - 博客园 (cnblogs.com))

解决算法

Ford-Fulkerson 算法(以下简称FF算法)

FF算法的核心是找增广路,直到找不到为止。(就是一个搜索，用尽可能多的水流填充每一个点，直到没有水用来填充，或者没有多余的节点让水流出去)。

但是这样的方法有点基于贪心的算法，找到反例是显而易见的，不一定可以得到正解。

为了解决这种问题，我们需要一个可以吃后悔药的方法——加反向边。

原本我们的DFS是一条路走到黑的，现在我们每次进入一个节点，把水流送进去，同时建立一个权值与我们送入的水流量相等，但是方向相反的路（挖一条路让水流能够反向流回来，相当于给水流吃一颗后悔药）。

我们给了FF算法一颗后悔药之后就可以让他能够找到正确的最大流。

Ford-Fulkerson算法的复杂度为\(O(e \times f)\) ,其中 \(e\) 为边数, \(f\)为最大流

上代码。

#include <iostream>

#include <cstring>

using namespace std;

#define INF 0x3f3f3f3f3f3f3f3f

typedef long long ll;

// Base

const int N= 256;

const int M= 8192*2;

// End

// Graph

int head[N],nxt[M],to[M];

ll dis[M];

int p;

inline void add_edge(int f,int t,ll d)

{

    to[p]=t;

    dis[p]=d;

    nxt[p]=head[f];

    head[f]=p++;

}

// End

int n,m,s,t;

// Ford-Fulkerson

bool vis[N];

ll dfs(int u,ll flow)//u是当前节点 , flow是送过来的水量

{

    if(u==t)// End,水送到终点了

        return flow;

    vis[u]=true;

    for(int i=head[u];i!=-1;i=nxt[i])

    {

        ll c;//存 送水下一个节点能通到终点的最大流量

        if(dis[i]>0 //如果水流还能继续流下去

            && !vis[to[i]]  //并且要去的点没有其他的水流去过

            && (c=dfs(to[i],min(flow,dis[i])))!=-1//根据木桶效应,能传给下一个节点的水量取决于当前节点有的水量与管道(路径)能够输送的水量的最小值

            //要保证这条路是通的我们才可以向他送水,不然就是浪费了

            ) {

                dis[i]-=c;//这个管道已经被占用一部分用来送水了,需要减掉

                dis[i^1]+=c;//给他的反向边加上相同的水量,送后悔药

                //至于为什么是这样取出反向边,下面有讲

                return c;

        }

    }

    return -1;

}

// End

int main()

{

    ios::sync_with_stdio(true);

    memset(head,-1,sizeof(head));// init

    cin>>n>>m>>s>>t;

    for(int i=1;i<=m;i++)

    {

        int u,v,w;cin>>u>>v>>w;

        add_edge(u,v,w);

        add_edge(v,u,0);//建立一条暂时无法通水的反向边(后面正向边送水后,需要加上相同的水量)

        //第一条边 编号是 0 ,其反向边为 1, 众所周知的 奇数^1=奇数-1, 偶数^1=偶数+1 ,利用这种性质 ,我们就可以很快求出反向边,或者反向边得出正向边(这里说的正反只是相对)

    }

    //Ford-Fulkerson

    ll ans = 0;

    ll c;

    //          假设我们的水无限多

    while((c=dfs(s,INF)) != -1) //把源点还能送出去的水全部都送出去,直到送不到终点

    {

        memset(vis,0,sizeof(vis)); //重新开始送没送出去的水

        ans+=c;//记录总的水量

    }

    cout<<ans<<endl;

    return 0;

}

可以看出效率比较低,我这里开了O2也过不了模板题。

Edmond-Karp 算法(以下简称EK算法)

上面FF算法太慢了,原因是因为FF算法太死脑筋了,非要等现在节点水灌满了,才会灌其他的(明明有一个更大的水管不灌)。另外他有时候还非常谦让,等到明明走到了,却要返回去等别人水灌好,再灌自己的。

其实,EK算法便是FF算法的BFS版本。复杂度为\(O(v \times e^2)\)​(复杂度这么高行得通吗，当然可以，事实上一般情况下根本达不到这么高的上限)。

那我就直接上代码了。

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

#define INF 0x3f3f3f3f3f3f3f3f

typedef long long ll;

// Base

const int N= 256;

const int M= 8192*2;

// End

// Graph

int head[N],nxt[M],to[M];

ll dis[M];

int p;

inline void add_edge(int f,int t,ll d)

{

    to[p]=t;

    dis[p]=d;

    nxt[p]=head[f];

    head[f]=p++;

}

// End

int n,m,s,t;

// Edmond-Karp

int last[N];

ll flow[N];//记录当前的点是哪条边通到来的,这样多余的水又可以这样送回去.

inline bool bfs() //水还能送到终点返回true,反之false

{

    memset(last,-1,sizeof last);

    queue <int > Q;

    Q.push(s);

    flow[s] = INF; //把起点的水量装填到无限大

    while(!Q.empty())

    {

        int k=Q.front();

        Q.pop();

        if(k==t)// End,水送到终点了

            break;

        for(int i=head[k];i!=-1;i=nxt[i])

        {

            if(dis[i]>0 //如果水流还能继续流下去

               && last[to[i]]==-1  //并且要去的点没有其他的水流去过,所以last[to[i]]还是-1

               ){

                last[to[i]]=i;  // 到 to[i]点 需要走 i这条边

                flow[to[i]]=min(flow[k],dis[i]);//根据木桶效应,能传给下一个节点的水量取决于当前节点有的水量与管道(路径)能够输送的水量的最小值

                Q.push(to[i]);  //入队

            }

        }

    }

    return last[t]!=-1;//能够送到终点

}

// End

int main()

{

    ios::sync_with_stdio(true);

    memset(head,-1,sizeof(head));// init

    cin>>n>>m>>s>>t;

    for(int i=1;i<=m;i++)

    {

        int u,v,w;cin>>u>>v>>w;

        add_edge(u,v,w);

        add_edge(v,u,0);//建立一条暂时无法通水的反向边(后面正向边送水后,需要加上相同的水量)

        //第一条边 编号是 0 ,其反向边为 1, 众所周知的 奇数^1=奇数-1, 偶数^1=偶数+1 ,利用这种性质 ,我们就可以很快求出反向边,或者反向边得出正向边(这里说的正反只是相对)

    }

    // Edmond-Karp

    ll maxflow=0;

    while(bfs())//把源点还能送出去的水全部都送出去,直到送不到终点

    {

        maxflow+=flow[t];

        for(int i=t;i!=s;i=to[last[i]^1])//还有多余的水残留在管道里,怪可惜的,原路送回去.

        {

            dis[last[i]]-=flow[t];  //这个管道已经被占用一部分用来送水了,需要减掉

            dis[last[i]^1]+=flow[t];    //给他的反向边加上相同的水量,送后悔药

            //至于为什么是这样取出反向边,上面有讲

        }

    }

    cout<<maxflow<<endl;

    //

    return 0;

}

于是我们AC了这题。

还能不能更快? Dinic算法

FF和EK算法都有个比较严重的问题.他们每次都只能找到一条增广路(到终点没有被堵上的路).Dinic算法不仅用到了DFS,还用的了BFS.但是他们发挥的作用是不一样的。

种类 作用
DFS 寻找路
BFS 分层(内容前置里有讲哦)

Dinic快就快在可以多路增广(兵分三路把你干掉),这样我们可以节省很多走重复路径的时间.当找到一条增广路后,DFS会尝试用剩余的流量向其他地方扩展.找到新的增广路。

就这???

当然不止,Dinic还有当前弧优化(前面也有哦)，总之就是放弃被榨干的路。

这样的一通操作之后，复杂度来到了\(O(v^2 \times e)\)​

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

#define INF 0x3f3f3f3f3f3f3f3f

typedef long long ll;

// Base

const int N = 256;

const int M = 8192 * 2;

// End

// Graph

int head[N], nxt[M], to[M];

ll dis[M];

int p;

inline void add_edge(int f, int t, ll d)

{

    to[p] = t;

    dis[p] = d;

    nxt[p] = head[f];

    head[f] = p++;

}

// End

int n, m, s, t;

//Dinic

int level[N], cur[N];

//level是各点到起点的深度，cur为当前弧优化的增广起点

inline bool bfs() //分层函数,其实就是个普通广度优先搜索，没什么好说的，作用是计算边权为1的图，图上各点到源点的距离

{

    memset(level, -1, sizeof(level));

    level[s] = 0;

    memcpy(cur, head, sizeof(head));

    cur[s]=head[s];

    queue<int> Q;

    Q.push(s);

    while (!Q.empty())

    {

        int k = Q.front();

        Q.pop();

        for (int i = head[k]; i != -1; i = nxt[i])

        {

            //还能够通水的管道才有价值

            if (dis[i] > 0 && level[to[i]] == -1)

            {

                level[to[i]] = level[k] + 1;

                Q.push(to[i]);

                if(to[i]==t) return true;

            }

        }

    }

    return false;

}

ll dfs(int u, ll flow)

{

    if (u == t)

        return flow;

    ll flow_now = flow; // 剩余的流量

    for (int i = cur[u]; i != -1 && flow_now > 0; i = nxt[i])

    {

        cur[u] = i; //当前弧优化

        //如果水流还能继续流下去   并且    是向更深处走的

        if (dis[i] > 0 && level[to[i]] == level[u] + 1)

        {

            ll c = dfs(to[i], min(dis[i], flow_now));

            if(!c) level[to[i]]=-1;  //剪枝，去除增广完毕的点

            flow_now -= c;  //剩余的水流被用了c

            dis[i] -= c;    //这个管道已经被占用一部分用来送水了,需要减掉

            dis[i ^ 1] += c;    //给他的反向边加上相同的水量,送后悔药

            //至于为什么是这样取出反向边,下面有讲

        }

    }

    return flow - flow_now; //返回用掉的水流

}

//End

int main()

{

    ios::sync_with_stdio(true);

    memset(head, -1, sizeof(head)); // init

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= m; i++)

    {

        int u, v, w;

        cin >> u >> v >> w;

        add_edge(u, v, w);

        add_edge(v, u, 0); //建立一条暂时无法通水的反向边(后面正向边送水后,需要加上相同的水量)

        //第一条边 编号是 0 ,其反向边为 1, 众所周知的 奇数^1=奇数-1, 偶数^1=偶数+1 ,利用这种性质 ,我们就可以很快求出反向边,或者反向边得出正向边(这里说的正反只是相对)

    }

    //Dinic

    ll ans = 0;

    while (bfs())

        ans += dfs(s, INF);

    cout << ans << endl;

    return 0;

}

这个算法如果应用在二分图里，复杂度为\(O(v \times sqrt(e))\)

参考文献

1.《算法竞赛进阶指南》作者：李煜东

2.《[算法学习笔记(28): 网络流](算法学习笔记(28): 网络流 - 知乎 (zhihu.com))》 作者：Pecco

3.《[Dinic当前弧优化 模板及教程](Dinic当前弧优化 模板及教程 - Floatiy - 博客园 (cnblogs.com))》作者：Floatiy

相关文章