本文主要是介绍[图论入门]网络最大流 - 增广路算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#1.0 基本概念

先来介绍一下这个基本概念。

网络流是算法竞赛中的一个重要的模型，它分为两部分：网络和流。

网络，其实就是一张有向图，其上的边权称为容量。额外地，它拥有一个源点和汇点。

流，顾名思义，就像水流或电流，也具有它们的性质。如果把网络想象成一个自来水管道网络，那流就是其中流动的水。每条边上的流不能超过它的容量，并且对于除了源点和汇点外的所有点（即中继点），流入的流量都等于流出的流量。

源点可以无限量的向外提供流量，而汇点可以无限量的接受流量。

#2.0 最大流

这是一个比较常见的问题，也是本篇博客主要讨论的问题。

假设源点提供的流量足够多，问汇点最多可以接收到多少流量。

#2.1 Ford-Fullkerson 算法

\(\texttt{Ford-Fullkerson}\) 算法（\(\texttt{FF}\) 算法）是一个最大流的基础算法，其核心思想为寻找图中的增广路（Augmenting Path），实际就是网络中从源点到汇点的仍有剩余流量的路径。

我们来看一个例子：

在上图中，\(1\to3\to2\to4\) 是一条增广路，我们可以用这条路来更新残量网络，这时网络变为了

但是不难发现，我们如果开始选择 \(1\to3\to4,\ 1\to2\to4\) 这两条增广路，所得到的答案会更优，所以我们如果想要反悔这一操作，那么，我们可以加入反向边。

反向边最初的容量为 \(0\)，但是如果该反向边对应的边容量减少了 \(a\)，那么就给反向边的容量加上 \(a\)，这样我们就可以进行反悔，上面的例子变为

于是就有了这样一条增广路

然后我们这张网络的最大流就求得了。

\(\texttt{Ford-Fullkerson}\) 找增广路的过程是 \(\texttt{DFS}\)，这里不加以实现。因为一（jue）般（dui）用不到。

#2.2 Edmond-Karp 算法

实际上，\(\texttt{Edmond-Karp}\) 算法（\(\texttt{EK}\) 算法）本身只是 \(\texttt{FF}\) 算法的 \(\texttt{BFS}\) 实现。但由于 \(\texttt{DFS}\) 找到的增广路可能是七拐八绕的，而 \(\texttt{BFS}\) 却可以保证找到的增广路是最短的，因而在实际的时间复杂度上有了一定的优化，而且省去了递归导致的一系列问题。

当然，反向边的编号可以是运用成对变换的方法，即 \(0\ \hat{}\ 1=1,1\ \hat{}\ 1=0,2\ \hat{}\ 1=3,3\ \hat{}\ 1=1,\cdots\) 同时，我们也需要记录我们找到的增广路，为了更新残量网络。时间复杂度为 \(O(ve^2).\)

const ll N = 100010;
const int INF = 0x3fffffff;

struct Edge{
    int u,v;
    int nxt;
    ll w;
};
Edge e[N << 1];

ll n,m,cnt,head[N],vis[N],incf[N],pre[N],s,t,maxflow;

inline ll Min(const ll &a,const ll &b){
    return a < b ? a : b;
}

inline void add(const int &u,const int &v,const ll &w){
    e[cnt].u = u;e[cnt].v = v;e[cnt].w = w;
    e[cnt].nxt = head[u];head[u] = cnt ++;

    e[cnt].u = v;e[cnt].v = u;e[cnt].w = 0;
    e[cnt].nxt = head[v];head[v] = cnt ++;
}

inline bool EK(){
    mset(vis,0);queue <int> q;
    q.push(s);vis[s] = true;
    incf[s] = INF;
    while (q.size()){
        int x = q.front();q.pop();
        for (int i = head[x];i != -1;i = e[i].nxt)
          if (e[i].w){
              if (vis[e[i].v]) continue;
              incf[e[i].v] = Min(incf[x],e[i].w);
              pre[e[i].v] = i;
              q.push(e[i].v);vis[e[i].v] = true;
              if (e[i].v == t) return true;
          }
    }
    return false;
}

inline void update(){
    int x = t;
    while (x != s){
        int i = pre[x];
        e[i].w -= incf[t];
        e[i ^ 1].w += incf[t];
        x = e[i ^ 1].v;
    }
    maxflow += incf[t];
}

int main(){
    mset(head,-1);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for (int i = 1;i <= m;i ++){
        int u,v;ll w;
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
    }
    while (EK()) update();
    printf("%lld",maxflow);
    return 0;
}

#2.3 Dinic 算法

\(\texttt{EK}\) 算法似乎已经能满足我们了。。。吗？如果是稠密图，看起来 \(\texttt{EK}\) 算法就要爆炸了，那么我们就需要更优的算法。

\(\texttt{Dinic}\) 算法采用了分层图的思想，将图中的每一个点按照距离源点的远近进行分层。每次查找增广路时仅找比当前节点层数加一的节点进行扩展。

分层时采用 \(\texttt{BFS}\)，保证分层远近的正确性，一个点能被分层的前提是通向这个点的边仍有残量，这样可以保证没有残量的边不会被遍历，当我们分层到汇点就可以结束了，因为其他的没被分层的点所在层数必然比汇点要远，根据我们上面的实现思路，这样的点是不会扩展到汇点的。

扩展采用 \(\texttt{DFS}\) 实现，所以不用 update() 函数，可直接进行更新。注意进行一次分层后可以进行多次找增广路的操作，直到不能找到新的流量。

还有一点小优化：

• 如果在 \(\texttt{DFS}\) 的过程中，发现某一点返回的可拓展的流量为 \(0\)，那么就可以将该点的层数设置为 \(0\)，因为显然已经不可能通过该点更新残量网络了。
• 记录一个 now[x]，表示点 \(x\) 当前可以从哪一条相连的边开始进行探索，在后面的过程中，到点 \(x\) 便可以从编号为 now[x] 的边开始。原因也很简单：探索某条边时必然会将当前分层图上从这条边能得到的流量都拿到，之后再次探索这条边就没有意义了。

const int N = 100010;
const int INF = 0x3fffffff;

struct Edge{
    int u,v;
    int nxt;
    ll val;
};
Edge e[N << 1];

int n,m,s,t;
ll maxflow;
int cnt,head[N],d[N],now[N];
queue <int> q;

inline void add(const int &u,const int &v,const ll &w){
    e[cnt].u = u;e[cnt].v = v;e[cnt].val = w;
    e[cnt].nxt = head[u];head[u] = cnt ++;

    e[cnt].u = v;e[cnt].v = u;e[cnt].val = 0;
    e[cnt].nxt = head[v];head[v] = cnt ++;
}

inline bool bfs(){
    mset(d,0);
    while (q.size()) q.pop();
    q.push(s);d[s] = 1;now[s] = head[s];
    while (q.size()){
        int x = q.front();q.pop();
        for (int i = head[x];i != -1;i = e[i].nxt)
          if (e[i].val && !d[e[i].v]){
              q.push(e[i].v);
              now[e[i].v] = head[e[i].v];
              d[e[i].v] = d[x] + 1;
              if (e[i].v == t) return true;
          }
    }
    return false;
}

inline ll dinic(int x,ll flow){
    if (x == t) return flow;
    ll rest = flow,k,i;
    for (i = now[x];(i != -1) && rest;i = e[i].nxt){
        if (e[i].val && d[e[i].v] == d[x] + 1){
            k = dinic(e[i].v,min(rest,e[i].val));
            if (!k) d[e[i].v] = 0;
            e[i].val -= k;e[i ^ 1].val += k;
            rest -= k;
        }
        now[x] = i;
    }
    return flow - rest;
}

int main(){
    mset(head,-1);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for (int i = 1;i <= m;i ++){
        int u,v;ll w;
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
    }
    ll flow = 0;
    while (bfs()) while (flow = dinic(s,INF))
      maxflow += flow;
    printf("%lld",maxflow);
    return 0;
}

时间复杂度为 \(O(v^2e)\)。值得注意的一点是，\(\texttt{Dinic}\) 算法在 二分图最大匹配 上使用的时间复杂度是 \(O(v\sqrt e)\)，优于匈牙利算法。

#3.0 将二分图匹配最大匹配转化为最大流

对于一张二分图，我们将左图和右图之间的边容量设为 \(1\)，在左边加一个源点，向左图所有点连一条容量为 \(1\) 的边，在右边加汇点，所有右图的点向汇点连一条容量为 \(1\) 的边，在该图上跑最大流，得到的结果就是该图的最大匹配。

正确性显然，不证。

参考资料

[1] 初探网络流：dinic/EK算法学习笔记 - hyfhaha

[2] 算法学习笔记(28): 网络流 - Pecco

这篇关于[图论入门]网络最大流 - 增广路算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！