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

//但是其实比优化后的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),是一棵树。记录每个点的前驱边(必然只有一条)。
大概代码长这样:

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

大概代码长这样:

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

3. 优缺点

优:

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

缺:

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

4. 例题

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

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

Binic代码:

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