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

//但是其实比优化后的 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 的身影。。。