写在前面

因为本人太菜，所以大部分东西都只有结论，没有证明。

以及如果真的想学习网络流的话，建议去看OI Wiki。

概述

一个网络 $G=(V,E)$ 是一张有向图，图中每一条边都有一个给定的权值 $c(x,y)$，称为边的容量，特别地，若 $(x,y)\notin E$，则 $c(x,y)=0$。图中还有两个特殊点，$S\in V$ 和 $T\in V(S\ne T)$，分别称为原点和汇点。

设 $f(x,y)$ 是定义在节点二元组 $(x\in V,y\in V)$ 上的实数函数，且满足：

  1. $f(x,y)\leq c(x,y)$，即容量限制；
  2. $f(x,y)=-f(y,x)$，即斜对称；
  3. $\forall x\ne S,x\ne T,\sum\limits_{(u,x)\in E}{f(u,x)}=\sum\limits_{(x,v)\in E}{f(x,v)} $，即容量守恒。

$f$ 就被称为网络的流函数。对于 $(x,y)\in E$，$f(x,y)$ 称为边的流量，$c(x,y)-f(x,y)$ 称为边的剩余容量。

$\sum\limits_{(S,v)\in E}{f(x,y)}$ 称为整个网络的流量，即 从源点发出的所有流量之和。

艹，终于抄完了。

最大流

描述

我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。

算法 Edmonds-Karp

若从原点到汇点有一条路径上各边的剩余容量都大于 $0$，则称这条路径为增广路。显然，可以让一股流沿着增广路从原点流至汇点。使网络的流量增大。

Edmonds-Karp 算法的思路就是不断通过 bfs 找到增广路，直到不存在增广路为止。

Edmonds-Karp 算法在寻找增广路的过程中，只考虑图中所有 $f(x,y)<c(x,y)$ 的边，算出各边剩余容量的最小值，将其累加到答案。

值得注意的是因为当一条边的流量 $f(x,y)>0$ 时，根据斜对称性质，它的反向边流量 $f(y,x)<0$，此时必有 $f(y,x)<c(y,x)$，故在实现中要考虑反向边。

时间复杂度 $O(\lvert V\rvert \lvert E\rvert^2)$。

因为没写过，所以无代码。

算法 Dinic

在任意时刻，网络中所有节点以及剩余容量大于 $0$ 的边构成的边叫残量网络，即 $G_f=(V,E_f)$，其中 $E_f={(u,v) \mid c_f(u,v)>0 }$。

考虑在增广前先对 $G_f$ 做 BFS 分层，即根据结点 $u$ 到源点 $S$ 的距离 $d_u$ 把结点分成若干层。令经过 $u$的流量只能流向下一层的结点 $v$，即删除 $u$ 向层数标号相等或更小的结点的出边，我们称 $G_f$ 剩下的部分为层次图（Level Graph）。形式化地，我们称 $G_L=(V,E_L)$ 是 $G_f=(V,E_f)$ 的层次图，其中 $E_L={(u,v)\mid(u,v)\in E_f,d_u+1=d_v}$

如果我们在层次图 $G_L$ 上找到一个最大的增广流 $f_b$，使得仅在 $G_L$ 上是不可能找出更大的增广流的，则我们称 $f_b$ 是 $G_L$ 的阻塞流（Blocking Flow）。

定义层次图和阻塞流后，Dinic 算法的流程如下。

  1. 在 $G_f$。
  2. 在 $G_L$ 上 DFS 出阻塞流 $f_b$。
  3. 将 $f_b$ 并到原先的流 $f$ 中，即 $f \leftarrow f + f_b$。
  4. 重复以上过程直到不存在从 $S$ 到 $T$ 的路径。

此时的 $f$ 即为最大流。

摆了，抄的OI Wiki上的

还有一个东西是当前弧优化，等会在代码里体现。

时间复杂度为 $O(\lvert V\rvert^2 \lvert E\rvert)$，求解二分图最大匹配为 $O(\lvert E\rvert \sqrt{\lvert V\rvert})$。

证明详见。

最大流可解决二分图最大匹配问题。

Code

#include<cstring>
#include<iostream>
#include<queue>
#define int long long
using namespace std;
struct sss
{
    int q,w,e,nxt;
}a[1000005];
int cnt,head[1000005],d[1000005],n,now[1000005],m,N,S,T;
queue<int>q;
void adde(int q,int w,int e)
{
    a[++cnt].q=q;
    a[cnt].w=w;
    a[cnt].e=e;
    a[cnt].nxt=head[q];
    head[q]=cnt;
    a[cnt++].q=w;
    a[cnt].w=q;
    a[cnt].e=0;
    a[cnt].nxt=head[w];
    head[w]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    while(q.size())q.pop();
    q.push(S);
    d[S]=1;
    now[S]=head[S];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=a[i].nxt)
        {
            if(a[i].e&&!d[a[i].w])
            {
                q.push(a[i].w);
                now[a[i].w]=head[a[i].w];
                d[a[i].w]=d[x]+1;
                if(a[i].w==T)return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==T)return flow;
    int rest=flow;
    for(int i=now[x];i&&rest;i=a[i].nxt)
    {
        now[x]=i;//当前弧优化（避免重复遍历从x出发不可达扩展的边）
        if(a[i].e&&d[a[i].w]==d[x]+1)
        {
            int k=dinic(a[i].w,min(rest,a[i].e));
            if(!k)d[a[i].w]=0;
            a[i].e-=k;
            a[i%2?i+1:i-1].e+=k;
            rest-=k;
        }
    }
    return flow-rest;
}
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&S,&T);
    for(int i=1;i<=m;i++)
    {
        int q,w,e;
        scanf("%lld%lld%lld",&q,&w,&e);
        adde(q,w,e);
    }
    int ans=0,flow=0;
    while(bfs())while(flow=dinic(S,1e18))ans+=flow;
    printf("%lld",ans);
}

最小割

割

对于一个网络流图 $G=(V,E)$，其割的定义为一种 点的划分方式：将所有的点划分为 $S$ 和 $T=V-S$ 两个集合，其中源点 $s\in S$，汇点 $t\in T$。

割的容量

我们的定义割 $(S,T)$ 的容量 $c(S,T)$ 表示所有从 $S$ 到 $T$ 的边的容量之和，即 $c(S,T)=\sum_\limits{u\in S,v\in T}c(u,v)$。

最小割

最小割就是求得一个割 $(S,T)$ 使得割的容量 $c(S,T)$ 最小。

根据最大流=最小割定理，最大流=最小割。（证明）

Code

同上

费用流

定义

给定一个网络 $G=(V,E)$，每条边除了有容量限制$c(u,v)$，还有一个单位流量的费用 $w(u,v)$。

当 $(u,v)$ 的流量为 $f(u,v)$ 时，需要花费 $f(u,v)\times w(u,v)$ 的费用。

$w$ 也满足斜对称性，即 $w(u,v)=-w(v,u)$。

则该网络中总花费最小的最大流称为 最小费用最大流，即在最大化 $\sum_\limits{(s,v)\in E}f(s,v)$ 的前提下最小化 $\sum_\limits{(u,v)\in E}(f(u,v)\times w(u,v))$。

反之称为 最大费用最大流，共称费用流。

费用流可解决二分图最大带权匹配问题。

算法

SSP（Successive Shortest Path）算法是一个贪心的算法。它的思路是每次寻找单位费用最小的增广路进行增广，直到图上不存在增广路为止。

如果图上存在单位费用为负的圈，SSP 算法正确无法求出该网络的最小费用最大流。此时需要先使用消圈算法消去图上的负圈。

实现

只需将 EK 算法或 Dinic 算法中找增广路的过程，替换为用最短路算法寻找单位费用最小的增广路即可。

Code

#include<cstring>
#include<iostream>
#include<queue>
#define int long long
using namespace std;
struct sss
{
    int q,w,e,r,nxt;
}a[1000005];
int cnt,head[1000005],d[1000005],n,now[1000005],m,N,S,T,vis[1000005],mx;
queue<int>q;
void adde(int q,int w,int e,int r)
{
    a[++cnt].q=q;
    a[cnt].w=w;
    a[cnt].e=e;
    a[cnt].r=r;
    a[cnt].nxt=head[q];
    head[q]=cnt;
}
bool spfa()
{
    memset(d,0x3f,sizeof(d));
    while(q.size())q.pop();
    q.push(S);
    d[S]=0;
    vis[S]=1;
    now[S]=head[S];
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];i;i=a[i].nxt)
        {
            if(a[i].e&&d[a[i].w]>d[x]+a[i].r)
            {
                now[a[i].w]=head[a[i].w];
                d[a[i].w]=d[x]+a[i].r;
                if(!vis[a[i].w])q.push(a[i].w),vis[a[i].w]=1;
            }
    }
    }
    return d[T]!=0x3f3f3f3f3f3f3f3f;
}
int dinic(int x,int flow)
{
    if(x==T)return flow;
    vis[x]=1;
    int rest=flow;
    for(int i=now[x];i&&rest;i=a[i].nxt)
    {
        now[x]=i;
        if(!vis[a[i].w]&&a[i].e&&d[a[i].w]==d[x]+a[i].r)
        {
            int k=dinic(a[i].w,min(rest,a[i].e));
            if(!k)d[a[i].w]=0;
            mx+=k*a[i].r;
            a[i].e-=k;
            a[i%2?i+1:i-1].e+=k;
            rest-=k;
        }
    }
    vis[x]=0;
    return flow-rest;
}
signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&S,&T);
    for(int i=1;i<=m;i++)
    {
        int q,w,e,r;
        scanf("%lld%lld%lld%lld",&q,&w,&e,&r);
        adde(q,w,e,r);
        adde(w,q,0,-r);
    }
    int ans=0,flow=0;
    while(spfa())while(flcanliangow=dinic(S,1e18))ans+=flow;
    printf("%lld %lld",ans,mx);
}

其他

判断二分图的必须边与可行边

首先使用网络流求出二分图的一组最大匹配，再在残量网络上面跑强连通分量。

若边 $(x,y)$ 是必须边，则 $(x,y)$ 流量为 $1$，并且在残量网络上属于不同的强连通分量。

若边 $(x,y)$ 是可行边，则 $(x,y)$ 流量为 $1$，或者在残量网络上属于相同的强连通分量。

后记

看这个还不如看OI Wiki。