举若学习网络流的note

AC_notonlyAC · 2025-09-18 09:08:55 · 算法·理论

网络流

定义

什么是网络流？OI wiki 上的定义长这样：

实际意思就是：一张有向图，有一个 源点 S 和 汇点 T ，每两条边之间都有一个容量，流经这条边的流量不能超过该边的容量（可以将容量看作水管的容积）。要求从源点流出去多少就要在汇点流回来多少（因此不能存在50的流量从50容量的边流到30容量的边被卡了20，只能有30的流量从50容量的边流到30容量的边）。流到一个点若有分叉可以对流量进行分配，分配不同的流量至不同的路径上。

可以类比着城市的水网图来理解。

最大流

最大流就是在这张网络上源点可以流出的最大流量。

偷一张模板的图：

本图中源点为 4，汇点为 3。

一种最大流的分配方式为：

因此最大流为 20 + 20 + 10 = 50 。这是一种方式。

有哪些算法可以实现呢？

先引入几个概念：

残量网络：指所有节点和当前状态下所有还有容量残余的边组成的子网络（子图）。

增广路：一条在残量网络上从起点到汇点的路径，即这条路径上的每条边都还有剩余容量（容量均不为 0）。

那么我们肯定要给所有仍然是增广路的路流流量，也就是给所有仍然是增广路的路增广。但很明显，有时这样的贪心是错的，比如：

我们可能会先选择 1 \to 2 \to 3 \to 4 这条路，但很明显，这样的流量只有 3，而选择 1 \to 3 \to 4 和 1 \to 2 \to 4 的流量为 6。这时我们可以在 2 和 3 之间建立一条反边，初始容量为 0，当一条边的容量减少时，让这条边的反向边增加对应的容量。因此，一次增广路经过了某条反向边，就相当于给原边退流了。

在这张图中，原先选择 1 \to 2 \to 3 \to 4 这条路流了 3 的流量，此时正向边 2 \to 3 的容量降至 2，反向边 3 \to 2 的容量就变成 3 了。此时再走一条 1 \to 3 \to 2 \to 4 的路，流过 3 的流量（相当于原来 2 \to 3 退流了），正好最大流就是 3 + 3 = 6。是不是很神奇呢！

在这样的图上，能增广就增广看起来就很对了。

Edmonds−Karp 算法

由此便诞生了一种较为暴力的算法：只要还有增广边就 bfs，不停止。时间复杂度是 O(nm^2) 的，具体操作见模版题P3376 的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,s,t,flag[2005][2005],tot=1;
ll head[10005],tail[10005],nxt[10005],vl[10005],dis[10005],pre[10005],ans;
void add(ll u,ll v,ll w)
{
    tail[++tot]=v;
    vl[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
  //建反边
    tail[++tot]=u;
    vl[tot]=0;
    nxt[tot]=head[v];
    head[v]=tot;
//上面tot=1就是为了凑{2,3}这样一对异或1为其反向边的一组边
}
bool vis[10005];
bool bfs()
{
    for(ll i=1;i<=n;i++) vis[i]=0;//每次操作都清空，只找一条路
    vis[s]=1;
    dis[s]=1e18;
    queue<ll> q;
    q.push(s);
    while(q.size())
    {
        ll u=q.front();
        q.pop();
        for(ll i=head[u];i;i=nxt[i])
        {
            if(vl[i]==0) continue;
            ll v=tail[i];
            if(vis[v]==1) continue;
            dis[v]=min(dis[u],vl[i]);
            pre[v]=i;
            q.push(v);
            vis[v]=1;
            if(v==t) return 1;
        }
    }
    return 0;
}
void update()
{
    ll x=t;
    while(x!=s)
    {
        ll v=pre[x];
        vl[v]-=dis[t];//让其始终减去整条路流量最小的容量
        vl[v^1]+=dis[t];
        x=tail[v^1];
    }
    ans+=dis[t];
}
int main()
{
    cin>>n>>m>>s>>t; 
    for(ll i=1;i<=m;i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        if(flag[u][v]==0)//判重边
        {
            add(u,v,w);
            flag[u][v]=tot-1;
        }
        else vl[flag[u][v]]+=w;
    }
    while(bfs()) update();//有就一直跑
    cout<<ans;
}

很明显，这样的时间复杂度不是很优，找一条增广路就要跑一遍图。

Dinic 算法

我们可以每次 bfs 给整个图分层，随后再利用 dfs 进行一次跑多条增广路进行增广。这样的时间复杂度为 O(n^2m)，稠密图比EK算法优很多，因此此算法更常用。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,s,t,tot=1,ans;
ll head[10005],tail[10005],nxt[10005],vl[10005],dis[10005];
void add(ll u,ll v,ll w)
{
    tail[++tot]=v;
    vl[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
    tail[++tot]=u;
    vl[tot]=0;
    nxt[tot]=head[v];
    head[v]=tot;
}
ll now[10005];
bool bfs()
{
    for(ll i=1;i<=n;i++) dis[i]=1e18;//dis指的就是每个点在哪一层
    dis[s]=0;
    now[s]=head[s];//这里采用当前弧优化
    queue<ll> q;
    q.push(s);
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        for(ll i=head[u];i;i=nxt[i])
        {
            ll v=tail[i];
            if(vl[i]==0) continue;
            if(dis[v]!=1e18) continue;
            q.push(v);
            now[v]=head[v];//这里采用当前弧优化
            dis[v]=dis[u]+1;
            if(v==t) return 1; 
        }
    }
    return 0;
}
ll dfs(ll x,ll sum)
{
    if(x==t) return sum;
    ll res=0;
    for(ll i=now[x];i&&sum;i=nxt[i])
    {
        now[x]=i;//当前弧优化
        ll v=tail[i];
        if(vl[i]>0&&(dis[v]==dis[x]+1))//有流量且是在x的下一层
        {
            ll k=dfs(v,min(sum,vl[i]));//k是当前最小的剩余容量 
            if(k==0) dis[v]=1e18;//剪枝，如果此路不通就没必要继续走下去了，不如直接删了
            vl[i]-=k;
            vl[i^1]+=k;
            res+=k;
            sum-=k;
        }
    }
    return res;
}
int main()
{
    cin>>n>>m>>s>>t;
    for(ll i=1;i<=m;i++)
    {
        ll u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    while(bfs())
    {
        ans+=dfs(s,1e18);//流量可以设成无穷大，后续也会被挤掉
    }
    cout<<ans;
}

注：当前弧优化指本次 bfs 时当遍历到 x 的第 i 条弧时前 i-1 条弧没有被遍历的需要了（该流的都留了），因此下一次直接从 x 的第 i 条弧开始遍历，可以省点时间。

最小费用最大流

顾名思义，就是在最大流的基础上加上最小费用，即每条边有容量和代价（流过这条边的流量与代价成正比），在满足求最大流的情况下还要满足费用最小。

很明显，最小费用实质上就是最短路，所以我们可以考虑把最短路和最大流结合起来。SPFA 和最大流都是利用 bfs 维护的，而且由于有反边，我们要将反边的费用设为负值，需要让 SPFA 来解决负环的问题，因此可以考虑与 SPFA 相结合（虽然 SPFA 很容易被卡）。

详情见代码：

#include<bits/stdc++.h>
#define ll int
using namespace std;
ll n,m,s,t,tot=1,ans,minc;
ll head[500005],tail[500005],nxt[500005],vl[500005],val[500005],dis[500005],vis[500005];
void add(ll u,ll v,ll w,ll c)
{
    tail[++tot]=v;
    vl[tot]=w;
    val[tot]=c;
    nxt[tot]=head[u];
    head[u]=tot;
    tail[++tot]=u;
    vl[tot]=0;
    val[tot]=-c;//反向边边权设为负数
    nxt[tot]=head[v];
    head[v]=tot;
}
ll now[500005];
bool spfa()
{
    memset(vis,0,sizeof(vis));
    for(ll i=1;i<=n;i++) dis[i]=1e9;
    for(ll i=1;i<=n;i++) now[i]=head[i];//这样初始化似乎更直观
    dis[s]=0;
    queue<ll> q;
    q.push(s);
    vis[s]=1;
    //cout<<s<<" ";
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        vis[u]=0;
        for(ll i=head[u];i;i=nxt[i])
        {
            ll v=tail[i];
            if(vl[i]==0) continue;
            if(dis[v]>dis[u]+val[i])
            {
                dis[v]=dis[u]+val[i];
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                    //cout<<v<<" ";
                }
            }
        }
    }
    if(dis[t]!=1e9) return 1;
    return 0;
}
ll dfs(ll x,ll sum)
{
    if(x==t) return sum;
    ll res=0;
    vis[x]=1;
    for(ll i=now[x];i&&sum;i=nxt[i])
    {
        now[x]=i;
        ll v=tail[i];
        if(vl[i]>0&&(dis[v]==dis[x]+val[i])&&!vis[v])//同dinic，将其进行分层，vis[v]或许是为了判负环防止死循环的
        {
            ll k=dfs(v,min(sum,vl[i]));
            if(k==0) dis[v]=1e9;
            vl[i]-=k;
            vl[i^1]+=k;
            res+=k;
            sum-=k;
            minc+=k*val[i];//最小费用在这里就可以算了
        }
    }
    vis[x]=0;
    return res;
}
int main()
{
    cin>>n>>m>>s>>t;
    for(ll i=1;i<=m;i++)
    {
        ll u,v,w,c;
        cin>>u>>v>>w>>c;
        add(u,v,w,c);
    }
    while(spfa())
    {
        ans+=dfs(s,1e9);
    }
    cout<<ans<<" "<<minc;
}