网络流初步 —— 最大流算法

概念定义

• 网络：带权有向图 $G=(V,E)$。

• 容量：边 $(u,v)\in E$ 的权值，记作 $c(u,v)$。

• 源点、汇点： $s\in v , t \in v ,(s\neq t)$。

• 流量：设 $f(u,v)$ 满足

  1. 容量限制：对每条边流量不超过容量，即$f(u,v)\le c(u,v)$

  2. 斜对称性：每条边容量与其相反边容量为0，即$f(u,v)=-f(v,u)$

  3. 流守恒性：除源点和汇点，流入每个点的流量与流出每个点的容量相同，即

     $$\forall x \in V-\{s,t\},\sum_{(u,v)\in E}f(u,x)=\sum_{(u,v)\in E}f(x,v)$$

  则 $f(u,v)$ 为这条边的容量。整个网络的容量 $f(s,t)$ 为 $\sum_{(s,v)\in E}f(s,v)$，即源点流出的流量总和。并有 $\sum_{(s,v)\in E}f(s,v)=\sum_{(v,t)\in E}f(v,t)$。

最大流

给定一张网络，求出源点流向汇点的最大流量。

Ford-Fulkerson 算法

我们先考虑如下一个朴素算法，在一个网络中，寻找源点到汇点的路径，且路径上每一点都满足 $f(u,v)<c(u,v)$，对此路径进行增流，我们定义这样的路径为增广路。重复此步骤，直到找不到路径为止。

我们考虑如下图左的一个网络，假设朴素算法第一次寻找到的路径为下图右红色箭头所示。可以发现，这时候已经找不到路径了，朴素算法得出结果为1，但真实最大流为2。

为了解决此问题，Ford-Fulkerson 算法引入了反向边，通过反向边，可以起到一个反悔作用，保证找到的一定就是最大流。

如下图，图中红色箭头为找到的增广路，黄色箭头为反向边。

我们规定反向边的容量为0，这样在对一条边进行增流时，只需同时对他的反向边进行减流即可。在实际进行操作时，我们会预先创建好所有反向边，方便进行处理。

为什么这样添加反向边就能反悔呢？我们看下图：
假设目前算法得出答案的状态是第一个，而最大流的状态是第二个。我们可以发现，第二个和第三个是完全等价的。故添加反向边就能达到一个随时反悔的作用。

这样的算法的复杂度是 $O(mk)$ 的。其中 $m$ 为边数，$k$ 为最大流流量。因为每次找增广路的复杂度为 $O(m)$，每次流量至少增加1。

Edmonds-Karp 算法

为了解决这个问题，Edmonds-Karp 算法在Ford-Fulkerson 算法上的基础上做了一个小改进：在寻找增广路时，通过BFS，找到最短路（忽略边权）。

在这篇论文中，严谨证明了若寻找增广路时是最短路，则最多进行增广 $O(nm)$ 轮，总复杂度 $O(nm^2)$。

在实现过程中，我们一般不会采用邻接矩阵存图（因为无法处理重边，这点到处理费用流时会很明显），我们采用一个 vector 存储所有的边（edges），并用 $n$ 个 vector 存储第 i 个点所有边在 edges 中的下标。

如此，我们只要依次存正向边和反向边，可以直接对这条边的下标异或1就可以得到它的反向边的下标（0^1=1,1^1=0;2^1=3,3^1=2;...）。数据结构如下代码。

struct Edge{
    int u,v;
    ll f,c;
};      
vector<Edge> edges;
vector<int> G[N];
void add_edge(int u,int v,int w){
    edges.push_back({u,v,0,w});
    edges.push_back({v,u,0,0});

    auto cnt = edges.size();
    G[u].push_back(cnt-2);
    G[v].push_back(cnt-1);
}

对于BFS过程，我们对每个节点记录 vis，fa，flow 三个数据，分别代表是否访问过，最短路的父节点以及从源点到该节点最多还能流的流量。

int s,t;
bool vis[N];
int fa[N];
ll flow[N];
bool bfs(){
    // 找最短路径
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    flow[s]=INF;
    while(!q.empty() && !vis[t]){
        auto u = q.front();q.pop();
        // 找到所有相连
        for(auto e:G[u]){
            auto edge = edges[e];
            if(edge.c - edge.f >0 && !vis[edge.v]){
                vis[edge.v]=1;
                fa[edge.v]=e;
                flow[edge.v] = min(flow[u],edge.c - edge.f);
                q.push(edge.v);
            }
        }
    }
    return vis[t];
}

EK算法流程如下

ll EK(){
    ll ans = 0;
    while(bfs()){
        int now = t;
        // 找出可行最大流量
        ll availableFlow = flow[t];
        // 修改流量
        while(now!=s){
            edges[fa[now]].f += availableFlow;
            edges[fa[now]^1].f -= availableFlow;
            now = edges[fa[now]].u;
        }
        ans += availableFlow;
    }
    return ans;
}

Dinic 算法

在实际应用中，我们更多采用的是速度更快的 Dinic 算法。

Dinic 算法要求在每次增广前用 BFS 将图分层，保证我们找到的增广路是最短的。

bool bfs(){
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s);
    vis[s]=1;
    d[s]=0;
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int i=0;i<G[u].size();i++){
            auto& e = edges[G[u][i]];
            if(!vis[e.v] && e.f<e.c){
                d[e.v]=d[u]+1;
                vis[e.v]=1;
                q.push(e.v);
            }
        }
    }
    return vis[t];
}

我们保证从 u 出发找增广路时，只找 d[v]==d[u]+1 的节点，保证增广路最短，然后进行 DFS 找增广路。

int cur[N];
ll dfs(int u,ll a){
    if(u==t || a==0) return a;
    ll flow = 0;
    for(int &i=cur[u];i<G[u].size();i++){
        auto& e = edges[G[u][i]];
        if(d[u]+1 == d[e.v]){
            auto f = dfs(e.v,min(a,e.c-e.f));
            e.f += f;
            edges[G[u][i]^1].f -= f;
            a -= f;
            flow += f;
            if(a==0) break;
        }
    }
    if(flow==0)d[u]=0;
    return flow;
}

使用 DFS 可以一次找出多条增广路。其中 dfs(u,a) 的意思是，以 u 为起点，在最多流入 a 流量的情况下，最多能流入汇点的流量。

注意第1，5行，我们定义了一个 cur 数组，代表该节点已经增广到第几条边了（因为一条边被增广过就不可能在被增广）。

Dinic 算法主流程如下：

ll dinic(){
    ll flow = 0;
    while(bfs()){
        memset(cur,0,sizeof(cur));
        flow += dfs(s,INF);
    }
    return flow;
}

这样，单轮增广复杂度 $O(nm)$，总共最多进行 $n$ 轮。 Dinic 算法的复杂度为 $O(n^2m)$，在稠密图上复杂度远超 EK 算法。

例题

洛谷P3376 【模板】网络最大流