网络流合集【1】：网络流相关算法

Splay_trees · 2025-01-19 22:10:53 · 算法·理论

我们之前提到过，匈牙利算法进行二分图匹配的时候，是在人工模拟“退流”的过程。

今天，我们将介绍网络流及题目中的网络流建模，进一步认识一类新的最优化问题——网络流问题。

0x01 最大流

想象一个城市的排污系统，所有的管道组成了一张有向图。

这个城市只有一个污水厂，坐落于风景秀丽的点 s ，在点 t 处有一条河，很多净化后的污水从 s 点冒出，流过管道，到了 t 点后就消失了。

现在给定每条管道单位时间内可以通过的最大水量，求怎样调配管道水量，可以让污水厂单位时间内排走污水的体积最大？

以上就是网络流问题中一类最简单的问题——最大流问题的基本模型。

插曲

一个网络是指一个特殊的有向图 G(V,E) ， \forall e(u,v) \in E 有一个权 c(u,v) 即流量。一个流是一个 E 到 \mathbb{Z} 或 \mathbb{R} 的函数，满足以下性质：

容量限制：0 \le f(u,v) \le c(u,v) 。
流守恒性：对于任意非源汇点的顶点 u ，其流进流出流量之和为 0 。

怎么做？

为了更好处理这个问题，我们可以转化。将每条管道 (u,v,w) 根据流守恒性拆分为两条对冲管道 (u,v,x)(v,u,y)，对冲的水相互可以抵消，只要 x-y\le w 就合法。初始置 x=w,y=0 。转化的目的是为了增广（反悔），这个稍后会提到。我们将转化后的图叫做一张 残量网络 。

还有一种截然不同的方法，不使用流守恒性，叫做 HLPP ，这个我不会，本文先不讲。

1) Ford-Fulkerson 算法

考虑这样一个莽撞的算法：

在残量网络上寻找 s \to t 的一条路径
统计路径边权最小值，加入总流量
删除对应边
重复 1-3 直到 s\to t 不存在路径
结束

但是这个算法是错误的。考虑：

对于右上角的这张图，假设我们第一步搜到了 1\to 2\to 3\to 4 这条路，那么我们删除这几条边，会发现求得的最大流是 1 ，但是肉眼可见最大流应该是 2 。

为什么会出现问题？因为我们没有留下反悔的余地。我们利用对冲管道，当 u \to v 的管道使用了 f 的流量，那么 v \to u 的反向边就应该空出 f 的流量。

这样，第一次增广以后，我们继续 DFS，可以 DFS 出一条 1 \to 3 \to 2 \to 4 的增广路，其中 3 \to 2 使用了反向边的 1 流量。

我们发现，当这两条增广路重合，将一正一反抵消，我们就得到了理想的 1\to 2 \to 4 和 1 \to 3 \to 4 两条流量，总流量也重回正轨，得到 2 的结果。

其实，根据增广路定理可以证明，这样反悔以后增广得到的结果确实是网络的最大流。如果使用 DFS 增广，我们就可以得到 Ford-Fulkerson 算法，也叫朴素增广算法，时间复杂度 O(nm^2) 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int e[205][205],n,m,s,t;
bool vis[205];
int stk[205],top;
int ans;
int flag;

void ford_fulkerson(int x)
{
    if(flag)
        return;
    stk[++top]=x;
    if(vis[x])
    {
        --top;
        return;
    }
    vis[x]=1;
    if(x==t)
    {
        int tmp=LLONG_MAX;
        int rt=top;
        while(rt>1)
        {
            tmp=min(tmp,e[stk[rt-1]][stk[rt]]);
            rt--;
        }
        ans+=tmp;
        rt=top;
        while(rt>1)
        {
            e[stk[rt-1]][stk[rt]]-=tmp;
            e[stk[rt]][stk[rt-1]]+=tmp;
            rt--;
        }
        flag=1;
        return;
    }
    for(int i=1; i<=n; i++)
    {
        if(e[x][i]!=0 && !flag && !vis[i])
        {
            ford_fulkerson(i);
        }
    }
    --top;
    return;
}

signed main()
{
    cin>>n>>m>>s>>t;
    for(int i=1; i<=m; i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e[u][v]+=w;
    }
    while(1)
    {
        flag=0;
        memset(vis,0,sizeof(vis));
        top=0;
        ford_fulkerson(s);
        if(!flag)
            break;
    }
    cout<<ans;
    return 0;
}

Ford-Fulkerson 由于其固有的回溯性质，所以可以多路增广来节省常数时间。

2) Edmonds-Karp 算法

核心思想：通过将 DFS 改换成 BFS 节省寻找增广路的时间到严格 O(m) ，时间复杂度 O(nm^2) 。其他原理和 Ford-Fulkerson 是一样的。

代码的坑过会再填。

3) Dinic 算法

如果我们想同时利用 DFS 的多路增广优势，和 BFS 的层序最优性——

我们可以进行 BDFS ！也就是说，先 BFS 出残量网络的层序，然后在 DFS 的时候限定下一步节点的层序，这样就可以在加速增广的同时多路增广了！

于是就有了 Dinic 算法。

但是 Dinic 除了增广以外还有一个十分厉害的优化：当前弧优化。在增广的时候使用邻接表，只要某一条边 DFS 完以后，这一次多路增广就已经跑满了这条边的流，所以可以从邻接表里（暂时）删除这条边。

Upd on 26/03/25：实际上当前弧优化是保证 Dinic 算法时间复杂度的一个部分，多路增广在此处只是常数优化。

可以证明，Dinic 算法的时间复杂度是 O(n^2 m) 的。但是由于其玄学的实现方式和网络流本身的限制，使得正式比赛中 Dinic 基本卡不掉，所以 SAP、ISAP、HLPP 等算法本篇暂且不提。

#include <bits/stdc++.h>
using namespace std;
const int N = 305,M=10005;
struct edge
{
    int to,nxt,w;
    edge(int to=0,int nxt=0,int w=0):to(to),nxt(nxt),w(w) {}
} e[M];
int head[N],top=1;
void add_edge(int u,int v,int w)
{
    e[++top]=edge(v,head[u],w);
    head[u]=top;
}

int m,n,k,s,t;

int level[N];
bool vis[N];
bool bfs()//广搜标记层次
{
    memset(vis,0,sizeof(vis));
    level[s]=1;
    level[t]=-1;
    list<int> q;
    q.push_back(s);
    vis[s]=1;
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        for(int i=head[k]; i; i=e[i].nxt)
        {
            if(!vis[e[i].to] && e[i].w!=0)
            {
                vis[e[i].to]=1;
                level[e[i].to]=level[k]+1;
                q.push_back(e[i].to);
            }
        }
    }
    return level[t]!=-1;
}

#define INF LLONG_MAX
int cur[N];
long long dfs(int x,long long res)
{
    long long ans = 0;
    if(x == t)
    {
        return res;
    }
    for(int i=cur[x]; i; i=e[i].nxt)
    {
        cur[x]=i;//当前弧优化
        if(e[i].w==0 || level[e[i].to] != level[x]+1) continue;
        int tmp=dfs(e[i].to,min(res-ans,1ll*e[i].w));
        if(tmp!=0)//增广成功
        {
            ans+=tmp;
            e[i].w-=tmp;
            e[i^1].w+=tmp;
      //没有返回，多路增广
        }
        if(ans==res)
        {
            return ans;//相当于取min(res,ans之和)
        }
    }
    if(ans==0)
        level[x]=-1;//炸点，相当于当前弧优化
    return ans;
}

long long dinic()
{
    long long ans=0;
    while(bfs())//标记层次，判断联通
    {
        memset(vis,0,sizeof(vis));
        for(int i=1; i<=n; i++) cur[i]=head[i];//还原邻接表
        ans+=dfs(s,INF);//增广
    }
    return ans;
}

int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add_edge(a,b,c);
        add_edge(b,a,0);
    }
    cout<<dinic();
    return 0;
}

0x02 最小费用最大流

每条边给定单位流量费用 w(u,v) ，求所有最大流中花费最小的那一个。

1) SSP 算法

考虑贪心在增广的时候用 Bellman-Ford (SPFA 也可以) 替换 Edmonds-Karp 算法里的 BFS 即可。

#include <bits/stdc++.h>
using namespace std;

const int N=5005,M=200005;
int n,m,s,t;
int top=1;
struct edge
{
    int u,v,w,f;
    edge(int u=0,int v=0,int w=0,int f=0):u(u),v(v),w(w),f(f){}
}e[M];

int answ,ansf;
int dis[N],inflow[N],pre[N];
#define INF 0x7f7f7f7f
bool bellman()
{
    memset(dis,0x7f,sizeof(dis));
    memset(inflow,0x7f,sizeof(inflow));
    memset(pre,-1,sizeof(pre));
    dis[s]=0;
    bool f;
    for(int i=1;i<=n;i++)
    {
        f=0;
        for(int j=2;j<=m+m+1;j++)
        {
            if(e[j].w!=0 && dis[e[j].v]>dis[e[j].u]+e[j].f)
            {
                f=1;
                dis[e[j].v]=dis[e[j].u]+e[j].f;
                inflow[e[j].v]=min(inflow[e[j].u],e[j].w);
                pre[e[j].v]=j^1;
            }
        }
        if(!f)break;
    }
    if(dis[t]==INF) return 0;
    for(int i=pre[t];~i;i=pre[e[i].v])
    {
        e[i^1].w-=inflow[t];
        e[i].w+=inflow[t];
    }
    return 1;
}

int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1; i<=m; i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        e[++top]=edge(a,b,c,d);
        e[++top]=edge(b,a,0,-d);
    }
    while(bellman())
    {
        answ+=inflow[t],ansf+=dis[t]*inflow[t];
    }
    cout<<answ<<' '<<ansf;
    return 0;
}

这种算法的时间复杂度是 O(nmf) ，是伪多项式复杂度。

还有一种 Primal-Dual 算法，是利用势能标记去除负权。