求无向图中的最大流

Author： Colin
发布时间：May 11, 2020
3008 views
No comments
380 words
Categories：编程记录技术杂烩

# 问题
将下面这篇文章中问题的条件修改为流量可以被分割，也就是最大流模型。
<div class="preview">
<div class="post-inser post box-shadow-wrap-normal">
<a href="https://blog.co1in.me/archives/31/" target="_blank" class="post_inser_a no-external-link no-underline-link">
<div class="inner-image bg" style="background-image: url(https://blog.co1in.me/usr/themes/handsome/assets/img/sj/4.jpg);background-size: cover;"></div>

<div class="inner-content" >
<p class="inser-title">用Dijkstra寻找最大带宽路径</p>
<div class="inster-summary text-muted">
问题一个计算机网络，计算机为节点，连接他们的线为无向边，每条边有一个流量上限。求从计算机s到t的最大带宽。s发出流...
</div>
</div>
</a>

</div>

</div>

样例输入
```
4 5 1 4
1 2 3
1 3 6
2 3 4
2 4 5
3 4 3
```

样例输出
```
8
```

## 建模

本题需要在无向图中求给定源点s到汇点t的最大流。

课本上的最大流是有向图，这里需要把无向边都转化为一对方向相反的有向边边，每对中两条边的容量是相等的，流量是互为相反数的，即如果u到v流量是w，则v到u流量自然是是-w。在增流的时候，按照搜索时形成的方向对对应的“顺向的边”进行读取和操作，“反向边”在修改流量时对称地“反向操作”即可，即顺向边增流delta，那么反向边退流delta。每条边可以增加的流量仍然为(c-w)，其中容量c>0。（如果w<0，那么这条有向边最大可增加c+|w|，相当于反向边的方向退流|w|，再给顺向边增流c（最大可以增到满）。）只要保证按照正确的方向直接读取与操作顺向边，在更新流时对称地操作反向边，每条边的w值就会合法，即落在[-c, c]区间。

## 算法

应用Edmond-Karp算法。主要操作是从s开始BFS、给到达的点标号、到达t后反过来更新流值。如果某次BFS不能达到t，则说明不存在增流路径，则已得到最大流。

具体来说，借助一个队列从s开始BFS，取出队列的首元素作为“基点”，给探到的点进行标记，内容是它的前驱（本次的“基点”），与到达此点时可增加的最大流。标记完成之后将其加入队列，继续标记其它与“基点”关联的点。标记完成之后，再取出队列的首元素作为“基点”，……（重复以上操作。）直到如果某次取出了t，说明找到一条增流路径，增大的流量为t的标记中的流量delta。于是以t为起始点，根据标记迭代找前驱、更新当前点……每次需要更新从前驱到当前点的顺向边（加上delta），再对称地更新从当前点到前驱的反向边（减去delta）。直到当前点为s，这一次增流完成。于是删除所有标记，重新从s开始BFS。重复操作多次之后，某一次队列中不曾取出t队列就空了，这时就不能再进行增流。这时s的邻边的流量和就是最大流。

## 实现

```c++
//  Created by Colin on 2020/05/01.
//  Copyright © 2020 Colin. All rights reserved.
//  https://blog.valderfield.com/archives/32/

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

const int maxn = 102;

struct Node
{
    int capacity;
    int forward;
};

class Edmond_Karp
{
public:
    Node (*graph)[maxn];
    int n, m, s, t;
    int maxflow;
    
    Edmond_Karp(const int _n, const int _m, const int _s, const int _t, Node (*_g)[maxn]):
        n(_n), m(_m), s(_s), t(_t), graph(_g)
    {
        maxflow = 0;
    }
    
    struct Label
    {
        int pre;
        int delta;
    };
    
    int work()
    {
        while (true)
        {
            bool reached = 0;
            Label label[maxn] = { 0 };
            bool viewed[maxn] = { 0 };
            queue<int> q;
            q.push(s);
            viewed[s] = 1;
            label[s].delta = 0x7ffffff;
            while (!q.empty())  // BFS
            {
                int now = q.front();
                q.pop();
                if (now != t)
                {
                    for (int i = 1; i <= n; i++)
                    {
                        if (!viewed[i] && graph[now][i].capacity > 0 && graph[now][i].forward < graph[now][i].capacity)
                        {
                            viewed[i] = 1;
                            q.push(i);
                            // label
                            label[i].pre = now;
                            label[i].delta = min(label[now].delta, graph[now][i].capacity - graph[now][i].forward);
                        }
                    }
                }//end of if
                else    // now == t
                {
                    reached = 1;
                    int delta = label[t].delta;
                    while (now != s)    // update the flow
                    {
                        int pre = label[now].pre;
                        graph[pre][now].forward += delta;
                        graph[now][pre].forward -= delta;
                        now = pre;
                    }
                    break;
                }
            }// end of while
            if (!reached)
                break;
        }// end of while
        // calculate the max flow
        for (int i = 1; i <= n; i++)
        {
            if (graph[s][i].capacity > 0)
                maxflow += graph[s][i].forward;
        }
        return maxflow;
    }
    
};

int main()
{
    Node graph[maxn][maxn] = { 0 };
    // memset(graph, -0x3f, sizeof(graph));
    int n, m, s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v].capacity = graph[v][u].capacity = w;
    }
    Edmond_Karp ek(n, m, s, t, graph);
    printf("%d\n", ek.work());
    
    return 0;
}

```

Last modification：June 4, 2021