网络流

Day_Tao · 2024-10-18 09:35:39 · 算法·理论

网络流，字面意思，就是在网络（图）上流动。流动肯定会存在源点（S）和汇点（T）。对于有向图 G，每条边都有一个容量，表示可以流过的上限，用 c(u,v) 表示，特别的，若 (u,v)\notin E，c(u,v)=0。每条边都有一个流量，用 f(u,v) 表示。将网络的流函数记作 f，整个网络的流量记为 |f|。|f|=\sum\limits_{u\in V}f(s,u)-\sum\limits_{u\in V}f(u,s)。不难发现几个性质：

容量限制：每条边的流量存在上限，即 0\le f(u,v)\le c(u,v)。
流守恒：对于一个非源汇点，流进来的等于流出去的，即 \forall u\neq S\wedge u\neq T，\sum\limits_{v\neq u}f(u,v)=\sum\limits_{v\neq u}f(v,u)。

我们定义一条边 (u,v) 的 剩余容量 c'(u,v)=c(u,v)-f(u,v)。剩余容量可以理解为当前边还能再流多少。

此处引入一个概念：增广路。增广路指存在一条从 S 到 T 的路径，满足路径上所有边的剩余容量都大于 0，这样就可以增加流量。寻找增广路的操作我们称为增广。其实这个网络最终的流

发现这种问题似乎很难解决，要考虑到每条边的容量以及怎么流，朴素暴力似乎都不好写（吗），所以我们再引入一个概念：反向边。

我们定义一条正向边 (u,v) 的反向边 (v,u)，反向边的流为正向边的流的相反数，即 f(v,u)=-f(u,v)。初始化的正向边的剩余容量为 c(u,v)，反向边的剩余容量为 0。注意到反向边的流怎么是负数。但是考虑到我们其实不关注 f(u,v) 的具体数值，我们关注的是 c'(u,v)，所以正向边流量增加，反向边流量减少就相当于正向边的剩余流量减少，反向边的剩余流量增加。形象的理解就是正向边流量增加，剩下可以流过去的就减少，反向边能流回来的就增加。所以与 f(v,u) 的数值无关。

反向边起到一个反悔的作用，走反向边其实就是一个正向边回流的操作。这样哪怕一条正向边在一次增广中的流量增加了，下一次增广如果经过了这条正向边的反向边也可以进行回流。

对于反向边的查找，链式前向星选手可以直接用异或的方式，但是对于我这种喜欢用领接表的选手可能就得复杂点，就要记录很多东西了。

另外，我们将当前 G 中的所有点以及非 0 的边（剩余容量非 0 的边）构成的子图称为残量网络。

下面详细介绍一下网络流。

最大流

模板：P3376 【模板】网络最大流

即求一个网络里的最大流量。

Edmonds–Karp 算法

（我们称之为 EK 算法）

注意，我们在跑最大流的时候的边权是剩余容量。

其实就是每次在残量网络中暴力 BFS 寻找增广路去增加流量，直到找不到一条增广路为止。对于每条增广路上的边权取最小，然后进行边权和答案的更新。边权的更新可以考虑记录每个点的前驱，对于当前走的边减小边权，对于当前走的边的反向边增加边权，单次 bfs 的时间复杂度为 O(m)，增广轮数的上限为 O(n,m)，这部分的证明可以参考oi-wiki（一坨/tuu）。所以说该算法复杂度为 O(nm^2)。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define mid ((l+r)>>1)
#define fi first
#define se second
#define SZ(a) ((int)a.size())
#define pc(a) putchar(a)
#define mp(a,b) make_pair(a,b)
typedef long long ll;
const int N = 200 + 5;
const int M = 5e3 + 5;
const int mod = 998244353;
const ll INFLL = LONG_LONG_MAX;
const int INF = INT_MAX;
inline void cmx(int&a,int b){a=max(a,b);}
inline void cmn(int&a,int b){a=min(a,b);}
inline void add(int&a,int b){a+=b;if(a>=mod)a-=mod;}
inline int rd()
{
    int x=0,y=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1;
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    return x*y;
}
struct Day_Tao{int v,id;}pre[N]; // 记录前驱 
int n,m,S,T,val[M<<1],fl[N][N],ans,dis[N];
// val 记录每条边的边权，下标用编号来记  dis 记录从 S 到当前点的最小边权
bool vis[N];
vector<Day_Tao>G[N];
queue<int>q;
inline bool bfs()
{
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++)vis[i]=0;
    q.push(S),vis[S]=1,dis[S]=INFLL;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(Day_Tao t:G[u])
        {
            int v=t.v,i=t.id; // 残存网络即不存在边权为 0
            if(!val[i]||vis[v])continue;vis[v]=1,q.push(v);
            dis[v]=min(dis[u],val[i]),pre[v]={u,i};if(v==T)return 1;
        } // 找到一条增广路就退出 
    }return 0;
}
inline void SOLVE()
{
    n=rd(),m=rd(),S=rd(),T=rd();
    for(int i=0,u,v,w;i<m;i++){
        u=rd(),v=rd(),w=rd();
        if(!fl[u][v])G[u].push_back({v,i<<1}),G[v].push_back({u,i<<1|1}),
            val[i<<1]=w,fl[u][v]=i<<1,fl[v][u]=i<<1|1;
        else val[fl[u][v]]+=w; // 这边判了一下重边，在模板题中可以优化，当然也可以不加
    }
    while(bfs())
    {
        int u=T;
        while(u!=S)
        {
            int i=pre[u].id,v=pre[u].v;
            val[i]-=dis[T],val[i^1]+=dis[T],u=v;
        }ans+=dis[T]; // 更新边权 
    }printf("%lld\n",ans);
    return ;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T=1;while(T--) SOLVE();return 0;
}

~~感觉写的比较丑，看 Dinic 的时候发现有比较优美的写法，这边懒得改了，稍微参考一下即可，反正 Dinic 比较常用（~~

Dinic 算法

发现 EK 每次跑一边残量网络只能找出一条增广路，非常不牛。所以我们考虑能不能对一个残量网络找出多条增广路。

Dinic 就能够在一个残量网络中找出多条增广路，思想就是分层图 + \operatorname{dfs}。

先跑分层图，按照到源点的经过的边数分层，使用 \operatorname{bfs}。然后 \operatorname{dfs} 去找增广路，每次只从当前点走到到下一层的点，找到汇点之后回溯，当前路径上的最小权值就是当前路径上的流。回溯的时候修改流的大小。当前残量网络中无法增广时重新寻找残量网络，直到找不到有 S 到 T 的残量网络为止。时间复杂度 O(n^2m)。

其中有一个操作用来确保时间复杂度的正确性，即 当前弧优化。考虑一个点的到下一层点的边数很多，那么对于一个残量网络进行多次 \operatorname{dfs} 时可能就会多次访问重复的边。而我们通过上述过程可以知道，对于一个节点的下一层已经访问过的点已经不可能找到新的增广路了，所以我们考虑维护一个指针 cur_u，表示当前点 u 的下一层访问到了哪个点。

注意到对于当前残量网络不存在一条增广路之后还会重新找残量网络的，不像我这么幽默没想到这个然后鱼鱼蒸了好久（

考虑证明时间复杂度正确性：不会证，oi-wiki。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define mid ((l+r)>>1)
#define fi first
#define se second
#define SZ(a) ((int)a.size())
#define pc(a) putchar(a)
#define mp(a,b) make_pair(a,b)
typedef long long ll;
const int N = 200 + 5;
const int M = 1e6 + 5;
const int mod = 998244353;
const ll INFLL = LONG_LONG_MAX;
const int INF = INT_MAX;
inline void cmx(int&a,int b){a=max(a,b);}
inline void cmn(int&a,int b){a=min(a,b);}
inline void add(int&a,int b){a+=b;if(a>=mod)a-=mod;}
inline int rd()
{
    int x=0,y=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar())if(c=='-')y=-1;
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
    return x*y;
}
struct Day_Tao{int v,w,id;};
vector<Day_Tao>G[N];
int n,m,S,T,dep[N],cur[N],ans,flow=0;
queue<int>q;
inline bool bfs()
{ // 找残量网络的分层图   
    for(int i=1;i<=n;i++)dep[i]=-1;
    while(!q.empty())q.pop();q.push(S),dep[S]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(Day_Tao i:G[u]){
            int v=i.v,w=i.w;
            if(dep[v]==-1&&w)dep[v]=dep[u]+1,q.push(v);
        }
    }for(int i=1;i<=n;i++)cur[i]=0;return (dep[T]!=-1);
}
int dfs(int u,int mn)
{ // 增广 
    if(u==T)return mn;
    for(int i=cur[u];i<SZ(G[u]);i++)
    { // 当前弧优化
        cur[u]=i;int v=G[u][i].v,w=G[u][i].w,id=G[u][i].id;
        if(dep[v]==dep[u]+1&&w){
            int res=dfs(v,min(w,mn));
            if(res){G[u][i].w-=res,G[v][id].w+=res;return res;}
            else dep[v]=-1; // 下面找不到就先给标上不能走，剪枝
        }
    }return 0;
}
inline void SOLVE()
{
    n=rd(),m=rd(),S=rd(),T=rd();
    for(int i=1,u,v,w,x,y;i<=m;i++)
        u=rd(),v=rd(),w=rd(),x=SZ(G[u]),y=SZ(G[v]),
        G[u].push_back({v,w,y}),G[v].push_back({u,0,x});
// 适合领接表宝宝体质的优秀写法，边的编号就记为加边之前的大小，这样就可以找到反向边了
    while(bfs())while((flow=dfs(S,INFLL)))ans+=flow;printf("%lld\n",ans);
    return ;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T=1;while(T--) SOLVE();return 0;
}