网络流学习笔记

AC_Lover · 2025-02-22 20:06:27 · 算法·理论

基本概念

流网络定义

有向图 G=(V,E)，存在源点 s，汇点 t。

每条边 (u,v)，有容量 c(u,v)。

可行流

定义

记为 f，相当于给每条边限制一个流过的水量。

满足是可行流的条件：

容量限制，即不能流过限制：

0\le f(u,v)\le c(u,v) \\

流量守恒，即流入等于流出：

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

可行流的流量

记为 |f|，相当于从源点S流出去的流量和。

|f|=\sum_{(s,v)\in E}f(S,v)-\sum_{(v,s)\in E}f(v,S)

最大流

即最大可行流。

残留网络

定义

针对可行流定义，可行流 f 的残留网络记为 G_f。

V^\prime=V \\ E^\prime=E\cup\{E的反向边\}

对于原来图里的边，其新的容量定义为其还能流过的流量，而对于反向边，定义为其原本的容量。

\forall (u,v)\in E, \\ \left\{\begin{matrix} c^\prime(u,v)=c(u,v)-f(u,v) \\ c^\prime(v,u)=f(u,v) \end{matrix}\right.

定理

记原来图的一个可行流为 f，针对其定义的残留网络的可行流为 f^\prime，则 (f+f^\prime) 也是原图的一个可行流。

即

|f+f^\prime|=|f|+|f^\prime|

增广路径

定义

在残留网络中，从 S 出发，沿着容量大于 0 的边走，到达 T 的一条简单路径。

割

定义

对于流网络 G=(V,E)，源点为 s，汇点为 t。

将 V 分成不重不漏的两部分 S,T，源点 s 属于一部分，汇点 t 属于另一部分，即满足 S\cup T=V,S\cap T=\emptyset 并且 s\in S,t\in T。

割的容量

记为 c(S,T)，

c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)

最小割

所有的割中，容量最小的割被成为最小割。

割的流量

记为 f(S,T)，

f(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in T}\sum_{v\in S}f(u,v)

割的流量一定不大于割的容量，即 f(S,T)\le c(S,T)。

割的流量的值一定等于 |f|，即 f(S,T)=|f|。

即

|f|=f(S,T)\le c(S,T)

\mathrm{maxflow}\le\mathrm{mincut}

最大流最小割定理

内容：

以下三个条件是等价的：

①一个可行流 f 是最大流。

②可行流 f 构造出来的残留网络中不存在增广路。

③存在割 [S,T] 使得 |f|=c(S,T)，即最大流等于最小割。

证明：

证① \Rightarrow ②

反证法，如果 f 是最大流，并且还存在 |f^\prime|>0，那么 |f+f^\prime|=|f|+|f^\prime|>|f|，即有更大的可行流，于是矛盾。原命题得证。
证③ \Rightarrow ①

要证 |f|=\mathrm{maxflow} ，考虑证明 |f|\le \mathrm{maxflow} 并且 |f|\ge \mathrm{maxflow}。由于最大流是最大的可行流，所以显然有 |f|\le\mathrm{maxflow}，而由 \mathrm{maxflow}\le c(S,T) 并且 |f|=c(S,T)，有 \mathrm{maxflow}\le |f|，所以 |f|=\mathrm{maxflow}。原命题得证。

并且 \mathrm{mincut}\le c(S,T)=|f|\le \mathrm{maxflow}，所以有 \mathrm{mincut}\le \mathrm{maxflow}，又因为有 \mathrm{maxflow}\le \mathrm{mincut}，所以 \mathrm{mincut}=\mathrm{maxflow}，即f是最大流时最小割等于最大流。
证② \Rightarrow ③

考虑构造。

构造 S 为从 s 出发在残留网络中沿着容量大于 0的边能走到的点的集合，T=V\backslash S，可以发现这是一个合法的割。

然后考虑一条从 S 中的点 u 到 T 中的点 v 的一条边 (u,v)，必然有 f(u,v)=c(u,v)，因为若 f(u,v)<c(u,v)，残留网络中此条边的容量为 c^\prime(u,v)=c(u,v)-f(u,v)>0，则此时 v 应是可达的，矛盾，所以必有 f(u,v)=c(u,v)。并且考虑一条从 T 中的点 v 走到 S 中的点 u 的一条边 (v,u)，必有 f(v,u)=0，因为如果 f(v,u)>0，则残留网络中此条边的反向边 (u,v) 的容量 c^\prime(u,v)=f(v,u)>0，则此时在残留网络中 u 应是可达的，矛盾，所以必有 f(v,u)=0。

于是又因为 |f|=f(S,T)，所以
|f|=f(S,T)\\ =\sum_{u\in S}\sum_{v\in T}f(u,v)-\sum_{u\in T}\sum_{v\in S}f(u,v) \\ =\sum_{u\in S}\sum_{v\in T}c(u,v)-0 \\ =\sum_{u\in S}\sum_{v\in T}c(u,v) \\ =c(S,T)
得到 |f|=c(S,T)，原命题得证。

于是最终得到① \Rightarrow ②，② \Rightarrow ③，③ \Rightarrow ①，所以①，②，③等价。

原命题得证。

费用流

定义

定义一个可行流的费用为：

\sum_{(u,v)\in E}f(u,v)w(u,v)

费用流：所有最大可行流中费用的最小/最大值。

求解方法

以最小费用最大流为例。

可以证明，每一次在残留网络上增广的时候在满足容量大于 0 的情况下，走 w(u,v) 构成的最短路就能求出最小费用最大流。

算法

最大流算法

EK

思路

不断找到增广路，更新残留网络。

假设在残留网络中找到了一条增广路，将新增的可行流 f^\prime 设为这条增广路中容量最少的一条边的容量，然后残留网络中这条增广路上所有正向边的流量减少 f^\prime，反向边增加 f^\prime，继续找增广路，直到找不到。

这样根据最大流最小割定理，求出的一定是最大流。

时间复杂度： O(nm^2)，实际远远达不到，一般处理 10^3\sim 10^4 规模的网络，在最大流中不常用。

基本代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1010,M=20010,INF=1e9;
int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N],pre[N];
bool vis[N];

void add(int u,int v,int c)
{
    e[idx]=v,f[idx]=c,ne[idx]=h[u],h[u]=idx++;
    e[idx]=u,f[idx]=0,ne[idx]=h[v],h[v]=idx++;
}

bool bfs()
{
    memset(vis,0,sizeof(vis));
    int hh=0,tt=-1;
    q[++tt]=S;
    vis[S]=true;
    d[S]=INF;
    while (hh<=tt)
    {
        int u=q[hh++];
        for (int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i];
            if (!vis[v] && f[i]>0)
            {
                vis[v]=true;
                d[v]=min(d[u],f[i]);
                pre[v]=i;
                if (v==T) return true;
                q[++tt]=v;
            }
        }
    }
    return false;
}

int EK()
{
    int maxflow=0;
    while (bfs())
    {
        maxflow+=d[T];
        for (int i=T;i!=S;i=e[pre[i]^1])
        {
            f[pre[i]]-=d[T];
            f[pre[i]^1]+=d[T];
        }
    }
    return maxflow;
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h,-1,sizeof(h));
    for (int i=1;i<=m;i++)
    {
        int u,v,c;
        cin >> u >> v >> c;
        add(u,v,c);
    }

    cout << EK() << "\n";

    return 0;
}

Dinic

思路

本质是 \mathrm{EK} 算法的优化。

引入了分层图的思想，每次用 \mathrm{bfs} 构建出分层图，然后用 \mathrm{dfs} 将所有可以增广的路径增广。

分层图的具体构建方式是对于每个点 u，求出源点 s 到其最短路 d_u，将 d_u 作为层的划分。

当前弧优化

在 \mathrm{dfs} 的过程中，假设当前的流量限制是 \mathrm{limit}，从 u 遍历到 v 增广后，如果这条边的流量已经达到了流量上界 \mathrm{limit}，那么下一次从 u 开始增广时点 v 就不用再次增广了。

因此可以记录一个 cur_u 表示当前点 u 增广从哪条边开始。这样在 u 遍历时从边 cur_u 开始遍历即可。而当点 u 遍历到边 i 时，i 前面的点一定已经流满了，所以此时 cur_u\leftarrow i。

时间复杂度： O(n^2m)，可处理规模 10^4\sim 10^5 的网络，是解决最大流的常用算法。

基本代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=10010,M=200010;
const int INF=1e9;
int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N];
int cur[N]; 

void add(int u,int v,int c)
{
    e[idx]=v,f[idx]=c,ne[idx]=h[u],h[u]=idx++;
    e[idx]=u,f[idx]=0,ne[idx]=h[v],h[v]=idx++;
}

bool bfs()
{
    memset(d,-1,sizeof(d));
    int hh=0,tt=-1;
    q[++tt]=S;
    d[S]=0;
    cur[S]=h[S];
    while (hh<=tt)
    {
        int u=q[hh++];
        for (int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i];
            if (d[v]==-1 && f[i]>0)
            {
                d[v]=d[u]+1;
                cur[v]=h[v];
                if (v==T) return true;
                q[++tt]=v;
            }
        }
    }
    return false;
}

int find(int u,int limit)
{
    if (u==T) return limit;
    int flow=0;
    for (int i=cur[u];i!=-1 && flow<limit;i=ne[i]) //满足没有达到流量上限
    {
        cur[u]=i; //当前弧优化
        int v=e[i];
        if (d[v]==d[u]+1 && f[i]>0)
        {
            int t=find(v,min(f[i],limit-flow));
            if (!t) d[v]=-1; //无法增广的标记不可用
            f[i]-=t,f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0,flow;
    while (bfs()) while (flow=find(S,INF)) maxflow+=flow;
    return maxflow;
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h,-1,sizeof(h));
    for (int i=1;i<=m;i++)
    {
        int u,v,c;
        cin >> u >> v >> c;
        add(u,v,c);
    }

    cout << dinic() << "\n";

    return 0;
}

费用流算法

EK

思路

此时用 \mathrm{incf}_u 表示到点 u 的增广路上的容量最小值， d_u 表示到点 u 的费用最短路的距离。

为了便于退流，在残留网络中的反向边的费用 w(v,u)=-w(u,v)。

然后将求最大流的 \mathrm{EK} 算法将 \mathrm{bfs} 换成求最短路的 \mathrm{spfa} 即可。

基本代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N=5010,M=100010;
const int INF=1e9;
int n,m,S,T;
int h[N],e[M],f[M],w[M],ne[M],idx;
int d[N],pre[N],incf[N];
bool vis[N];

void add(int u,int v,int c,int cost)
{
    e[idx]=v,f[idx]=c,w[idx]=cost,ne[idx]=h[u],h[u]=idx++;
    e[idx]=u,f[idx]=0,w[idx]=-cost,ne[idx]=h[v],h[v]=idx++;
}

bool spfa()
{
    memset(d,0x3f,sizeof(d));
    memset(incf,0,sizeof(incf));
    memset(vis,0,sizeof(vis));
    queue<int> q;
    d[S]=0;
    incf[S]=INF;
    q.push(S);

    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=false;
        for (int i=h[u];i!=-1;i=ne[i])
        {
            int v=e[i];
            if (f[i]>0 && d[v]>d[u]+w[i])
            {
                d[v]=d[u]+w[i];
                pre[v]=i;
                incf[v]=min(incf[u],f[i]);
                if (!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    return (incf[T]>0);
}

void EK_mcmf(int &flow,int &cost)
{
    flow=0;
    cost=0;
    while (spfa())
    {
        int t=incf[T];
        flow+=t,cost+=d[T]*t;
        for (int i=T;i!=S;i=e[pre[i]^1])
        {
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}

int main()
{
    cin >> n >> m >> S >> T;
    memset(h,-1,sizeof(h));
    for (int i=1;i<=m;i++)
    {
        int u,v,c,cost;
        cin >> u >> v >> c >> cost;
        add(u,v,c,cost);
    }

    int flow,cost;
    EK_mcmf(flow,cost);
    cout << flow << " " << cost << "\n";

    return 0;
}