//其实应该是因为常数小所以跑得比较快吧

//但是其实比优化后的 Dinic 还是慢的,所以 dalao 可以不用看这篇文章了

//其实写这篇文章主要是因为蒟蒻 XZY 被骗了所以 “作文以记之”

0. 引言

Binic 算法,即:“比你快”算法。

在蒟蒻 XZY 被骗了(可能是 Ta 自己看教程没看清)以后应运而生的一种算法。

最初和 Dinic 算法一样用 bfs+dfs 实现。

后来蒟蒻 XZY 看 HZWER 的题解时发现可以用 For 循环代替 dfs 来减小常数,发展成为目前的 bfs+for 循环实现。

1. 简介

一种网络流算法。

可以用来求最大流、最小费用最大流等经典问题。

实测发现:

  • 跑的比 dfs 的增广路一般快很多(比如 dfs 的增广路会超时的 “网络吞吐量” 那题用 Binic 能过)
  • 在数据不是特别大时和 Dinic 差不多。
  • 历史上存在关于蒟蒻 XZY 出了一道网络流模板题,随机数据较大结果把不加优化的 Dinic 卡成 0 分但是 Binic 却能不加任何优化地超快速过掉。

2. 实现

类似于 Dinic(本身就是蒟蒻 XZY 被坑了写了假的 Dinic),先跑一边 bfs,建立最短路网络(每条边长度为 1),是一棵树。记录每个点的前驱边(必然只有一条)。
大概代码长这样:

bool bfs()
{
    while(!que.empty())que.pop();//清空队列
    memset(book,0,sizeof(book)),que.push(0),book[0]=1;//加入源点 (0)
    while(!que.empty())
    {
        int F=que.front();que.pop();
        for(vector<int>::iterator i=g[F].begin();i!=g[F].end();i++)
            if(!book[e[*i].v]&&e[*i].c)
                from[e[*i].v]=*i,que.push(e[*i].v),book[e[*i].v]=1;//from[i] 是点 i 的前驱边的编号
        if(book[T])return 1; //T 为汇点,如果到达汇点说明找到了增广路可直接返回
    }
    return 0;
}

然后 For 循环找出增广路的流量,并且更新网络。

大概代码长这样:

void mxf()
{
    int MX=INT_MAX;
    for(int i=from[T];i!=-1;i=from[e[i].u])MX=min(MX,e[i].c);//获取流量
    for(int i=from[T];i!=-1;i=from[e[i].u])e[i].c-=MX,e[i^1].c+=MX;//更新路径
    ans+=MX;//统计答案
}

那么跑最大流大概就是这样:

while(bfs())mxf();

3. 优缺点

优:

  • 代码量较少(其实少不了多少)
  • 容易想
  • 不容易出错
  • 我编不下去了

缺:

  • 如果增广路过多就 GG 了。

4. 例题

「网络流 24 题」最长递增子序列 LOJ – 6005
传送门= ̄ω ̄=

具体做法已经在这篇博客->传送门= ̄ω ̄=讲过了,这里不做过多赘述。

Binic 代码:

#include <bits/stdc++.h>
using namespace std;
struct edge{int u,v,c;}e[1000005];
int n,h[505],f[505],s=1,T,cnt,from[1005],ans;
vector<int> g[1005];
bool book[1005];
queue<int> que;
void adde(int a,int b,int c)
{
    g[a].push_back(cnt),e[cnt++]=(edge){a,b,c};
    g[b].push_back(cnt),e[cnt++]=(edge){b,a,c};
}
bool bfs()
{
    while(!que.empty())que.pop();
    memset(book,0,sizeof(book)),que.push(0),book[0]=1;
    while(!que.empty())
    {
        int F=que.front();que.pop();
        for(vector<int>::iterator i=g[F].begin();i!=g[F].end();i++)
            if(!book[e[*i].v]&&e[*i].c)
                from[e[*i].v]=*i,que.push(e[*i].v),book[e[*i].v]=1;
        if(book[T])return 1; 
    }
    return 0;
} 
void mxf()
{
    int MX=INT_MAX;
    for(int i=from[T];i!=-1;i=from[e[i].u])MX=min(MX,e[i].c);
    for(int i=from[T];i!=-1;i=from[e[i].u])e[i].c-=MX,e[i^1].c+=MX;
    ans+=MX;
}
int main()
{
    scanf("%d",&n),T=n<<1|1,from[0]=-1;
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)if(h[j]<=h[i])
            s=max(s,f[i]=max(f[i],f[j]+1));
    }
    printf("%d\n",s);
    for(int i=1;i<=n;i++)if(f[i]==1)adde(0,i,1);
    for(int i=1;i<=n;i++)if(f[i]==s)adde(i+n,T,1);
    for(int i=1;i<=n;i++)adde(i,i+n,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(h[j]<=h[i]&&f[j]+1==f[i])adde(j+n,i,1);
    while(bfs())mxf();
    printf("%d\n",ans),g[0].clear(),g[T].clear();
    for(int i=1;i<=n;i++)g[i].clear(),g[i+n].clear();
    ans=cnt=0,adde(1,1+n,1e8),adde(n,n<<1,1e8);
    if(f[1]==1)adde(0,1,1e8);
    if(f[n]==s)adde(n<<1,T,1e8);
    for(int i=2;i<=n;i++)if(f[i]==1)adde(0,i,1);
    for(int i=1;i<n;i++)if(f[i]==s)adde(i+n,T,1);
    for(int i=2;i<n;i++)adde(i,i+n,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(h[j]<=h[i]&&f[j]+1==f[i])adde(j+n,i,1);
    while(bfs())mxf();
    printf("%d\n",ans);
    return 0;
}

你可以在本博客很多蒟蒻 XZY 写的网络流的博客中看到 Binic 的身影。。。

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

Night2002 · 2018年5月10日 4:57 下午

好像多路增广+当前弧优化会更优一点?虽然好像确实比较难写的说。

    XZYQvQ · 2018年5月14日 3:03 下午

    啊,本来就是这样的啦。。。
    只是 xzy 原本学错了算法然后写了博客然后不忍心删掉就。。。发上来啦。。。
    显然真正的 Dinic 更快嘛~

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注