题解 P4722 【模板】最大流 加强版 / 预流推进

· · 题解

2023.7.14 upd : 修改错别字。

本题目前理论复杂度最快方法。

超额缩放预流推进 EXCESS SCALING

全文

[3]A FAST AND SIMPLE ALGORITHM FOR THE MAXIMUM FLOW PROBLEM 1988

方法

Ahuja and Orlin 在 1988 年提出使用名为 Excess Scaling 的技巧把通用预流推进非饱和推流的次数从 O(n^2m) 降至 O(n^2\log U)。

类似 Binary Blcking Flow 算法对值域的缩放，我们进行 K=\lceil \log U\rceil +1 轮 Scaling，在每一轮中，我们定义 \Delta 为比所有超额流都大的最小 2 的幂，每一轮 Scaling 结束时 \Delta 减半。

在一次 Scaling 中，我们只考虑超额流大于 \Delta/2 的节点进行推流，并选择其中标号最小的节点，确保推到一个拥有较小超额流的节点去。

在 8n^2 次非饱和推流之后，不再有超额流大于 \Delta/2，一次 Scaling 结束。

在最多 K 次 Scaling 操作后，所有的节点超额流都会降至 0，至此我们可以得到最大流。

具体的，我们使用链表对每个标号的超额流足够大的点进行存储，每次去有点的最小标号中任意点推一次流，并更新当前弧。

当一个点无法推流时重贴标签并重置当前弧。

本算法复杂度正确性基于无重边和自环，因此预处理合并重边，去掉自环。

伪代码

实现相关

该算法饱和推流一共 O(nm) 次，非饱和推流一共 O(n^2\log U) 次。

时间复杂度为 O(nm+n^2\log U)，并可以调整 \Delta/ \beta 的 \beta\ge 2 这个参数变为 O(nm+\beta n^2\log_{\beta}U)。

该算法按 OI 的简单化实现方式常数巨大无比，千万不要考场使用。

[评测记录]

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <map>
#include <ctime>

#define int long long

using namespace std;

int res=0;

int K,level;
const int inf=(long long)1<<40;
int n,m,s,t;
struct edge
{
    int to,val,next;
}e[1200005];
int cnt=1,head[1200005],now[1200005];
void add(int x,int y,int z)
{
    cnt++;
    e[cnt].to=y;
    e[cnt].val=z;
    e[cnt].next=head[x];
    now[x]=head[x]=cnt;
}

int h[120005],w[120005],cnth[120005];
queue<int>list[120005];
queue<int>qq;
int book[120005];
void bfs()
{
    memset(h,0x3f,sizeof(h));
    h[t]=0;
    qq.push(t);
    while(!qq.empty())
    {
        int u=qq.front();
        qq.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i^1].val&&h[u]+1<h[v])
            {
                h[v]=h[u]+1;
                if(book[v]==0)
                {
                    qq.push(v);
                    book[v]=1;
                }
            }
        }
    }
}

void push_relabel(int x,int Delta)
{
    int i;
    int found=0;
    for(i=now[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if(h[x]==h[v]+1&&e[i].val)
        {
            found=1;
            break;
        }
        else
        {
            now[x]=e[i].next;
        }
    }
    if(found==1)
    {
        int v=e[i].to;
        int flow=min(e[i].val,w[x]);
        if(v!=t)flow=min(flow,Delta-w[v]);
        e[i].val-=flow;
        e[i^1].val+=flow;
        w[x]-=flow;
        w[v]+=flow;
        if(w[x]<=Delta/2)list[level].pop();
        if(w[v]>Delta/2&&v!=s&&v!=t)
        {
            list[h[v]].push(v);
            level--;
        }
    }
    else
    {
        res++;
        list[level].pop();
        cnth[level]--;
        if(cnth[level]==0)
        {
            for(int i=1;i<=n;i++)
            {
                if(h[i]>level&&i!=s&&i!=t&&h[i]<n+1)
                {
                    h[i]=n+1;
                }
            }
        }
        int minn=inf;
        for(int i=head[x];i;i=e[i].next)
        {
            int to=e[i].to;
            if(e[i].val)
            {
                minn=min(minn,h[to]);
            }
        }
        h[x]=minn+1;
        if(minn==inf)h[x]=n+1;
        if(h[x]<=1200000)cnth[h[x]]++;
        if(h[x]<=1200000)list[h[x]].push(x);
        now[x]=head[x];
    }
}

int Excess_Scaling()
{
    bfs();
    if(h[s]==0x3f3f3f)return 0;
    h[s]=n;
    for(int i=1;i<=n;i++)
    {
        if(h[i]<0x3f3f3f)
        {
            cnth[h[i]]++;
        }
    }
    for(int i=head[s];i;i=e[i].next)
    {
        int to=e[i].to,val=e[i].val;
        if(val)
        {
            e[i].val-=val;
            e[i^1].val+=val;
            w[s]-=val;
            w[to]+=val;
        }
    }
    for(int k=1;k<=K;k++)
    {
        int Delta=(long long)1<<(K-k);
        for(int i=1;i<=n;i++)
        {
            if(w[i]>Delta/2)
            {
                if(h[i]<=1200000)list[h[i]].push(i);
            }
        }
        level=1;
        while(level<=n)
        {
            if(list[level].empty())level++;
            else
            {
                int x=list[level].front();
                push_relabel(x,Delta);
            }
        }
        for(int i=1;i<=32;i++)
        {
            while(!list[i].empty())
            {
                list[i].pop();
            }
        }
    }
    return w[t];
}

signed main()
{
    int i,j,k;
    ios::sync_with_stdio(0);
    cin>>n>>m>>s>>t;
    for(i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if(x==y)continue;
        add(x,y,z);
        add(y,x,0);
    }
    K=31;
    cout<<Excess_Scaling();
    return 0;
}