最大流

[Ir1d]

https://oi-wiki.org/graph/flow/max-flow/

[AngeloSalsas]

%%%感觉好简单

[sshwy]

@AngeloSalsas
%%%感觉好简单

TQLTQL

[SupritYoung]

tql

[qinmaye]

增广路那边流量20 30那些是不是写错了，图上并没有20 30这些值

[thallium]

为啥用dinic的板子做HDU4280超时了……

[UMP40]

@thallium
为啥用dinic的板子做HDU4280超时了……

n，m是1e5的吧，你可以试着优化一下常数或改用HLPP

[Early0v0]

@qinmaye
增广路那边流量20 30那些是不是写错了，图上并没有20 30这些值

图片链接咕了，已修复

[lucifer1004]

HLPP的模板在洛谷上超时？

[yanjinbin]

这最大流这一小节也太简单了吧，没有Ref, 最多只能做个回忆性的提纲啊，无法作为学习材料啊

[Enter-tainer]

@yanjinbin hello~如果有好的想法欢迎开pr补充

[Saigyouji-Yuyuko]

ISAP的模板做草地排水WA了QAQ

[ywxktc]

ISAP模板忽略了一种情况：如果图中存在孤立的点x，那么其d[x]值是未定义的（因为没有初始化数组d[]）。
因此，当我们执行for (int i = 0; i < n; i++) num[d[i]]++;时，会发生段错误。

我的修改如下，在BFS中，将数组d[]初始化为n。这是因为非孤立点的d值不会超过n，所以我们将孤立的点放在num[n]是没有问题的。

  bool BFS() {
    memset(vis, 0, sizeof(vis));
    fill(d, d+n, n); // 此处是修改
    queue<int> Q;
    Q.push(t);
    vis[t] = 1;
    d[t] = 0;
    while (!Q.empty()) {
      int x = Q.front(); Q.pop();
      for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i] ^ 1];
        if (!vis[e.from] && e.cap > e.flow) {
          vis[e.from] = 1;
          d[e.from] = d[x] + 1;
          Q.push(e.from);
        }
      }
    }
    return vis[s];
  }

PS：使用时，记得调用init。

测试通过了P3376 【模板】网络最大流

[jpy-cpp]

txdy
tql
orz
%%%

[CreMicro]

dinic算法模板中dfs中的cur数组是什么？整个模板中除了memset赋值为0外没有任何操作

[Early0v0]

@CreMicro
dinic算法模板中dfs中的cur数组是什么？整个模板中除了memset赋值为0外没有任何操作

这个是当前弧优化。cur 数组指向目前已经扫描过哪些边。

cur 数组是有更改的，在 dfs() 的 for 循环中：int &i=cur[x] 一句。

[cqbzly]

为什么最大流集合中的每条路径不小于 $\sqrt{n}$ 呢 （抱歉我不会用 @）

[abcdhhhh]

@cqbzly
为什么最大流集合中的每条路径不小于 $\sqrt{n}$ 呢 （抱歉我不会用 @）

因为每一轮增广，增广路的长度都是严格递增的。经过 $\sqrt{n}$ 轮增广之后，增广路的长度就大于 $\sqrt{n}$ 了。

[yaoxi-std]

HLPP 模版代码似乎会在 $h(u)=+\infty$ 的时候给 $gap$ 数组进行更新导致 RE。

hack数据如下：

4 3 1 4
1 2 1000
2 4 2000
1 3 1000

应该要判断一下的

[argvchs]

以下是 @yaoxi-std 的数据，源点为 1，汇点为 4，但是点 3 不能到达汇点，于是 ht[3] = INF

模板代码中第 32 行在初始化时没有检查高度，导致没有被 continue 掉

if (!w || init == false && ht[u] != ht[v] + 1)  // 初始化时不考虑高度差为1
  continue;

然后在 36 行这里，是因为 B[ht[3]] 越界导致 RE

if (v != s && v != t && !ex[v]) B[ht[v]].push(v), level = max(level, ht[v]);

所以 gap 数组没有问题但是 B 数组越界了

[argvchs]

只要把 32 行改成这样就可以了（在后面加上 ht[v] == INF）

if (!w || init == false && ht[u] != ht[v] + 1 || ht[v] == INF)

[2005ZHW]

ht[u] == INF应该改为ht[v] == INF吧，这里访问的是节点v

[argvchs]

啊

确实 w

[WineChord]

有一篇 paper 提供了 $O(m^{1+o(1)})$ 均摊复杂度的算法（$m$ 为边数），先 mark 一下：https://arxiv.org/abs/2203.00671

[IceDream61]

今天（2022年06月14日），机器之心报道——最大流算法有个新突破，可以快到几乎线性的时间（图越大越接近O(M)），详见：
https://finance.sina.com.cn/tech/2022-06-14/doc-imizmscu6737843.shtml?finpagefr=p_114
不过，目前该算法还比较长而又复杂，或许过几年会逐渐简化并广泛应用开来。

[felixesintot]

@IceDream61
今天（2022年06月14日），机器之心报道——最大流算法有个新突破，可以快到几乎线性的时间（图越大越接近O(M)），详见：
https://finance.sina.com.cn/tech/2022-06-14/doc-imizmscu6737843.shtml?finpagefr=p_114
不过，目前该算法还比较长而又复杂，或许过几年会逐渐简化并广泛应用开来。

dalaodalao

[Nanarikom]

PR4663：由于原版本错误太多，Ford-Fulkerson 增广、Edmonds-Karp 算法、Dinic 算法三节已经重写。希望对你有所帮助！

[cxm1024]

Dinic 的讲解中提到

实际上，当前弧优化是用于保证 Dinic 时间复杂度正确性的一部分

然而后面的参考代码并没有写当前弧优化。

[argvchs]

？写了啊
cur 就是当前弧优化了

[Nanarikom]

注意 i 是 cur[u] 的引用

[383494]

void relabel(int u) {
  ht[u] = INF;
  for (int i = h[u]; i; i = e[i].nex)
    if (e[i].v) ht[u] = min(ht[u], ht[e[i].t]);
  ++ht[u];
}

这里为什么不用最低的点高度+1

[383494]

是我看错了orz 下面一行有++

[qz-i]

去年的那个线性算法是tcs，先不说常数有多大，现在根本就实现不了/_ \

12年有一个 $O(NM)$ 的算法，到现在也没有普及

[369Pai]

卡 Dinic / EK https://www.zhihu.com/question/266149721

[ShawxingKwok]

真有人只靠这里的文档就能看懂吗？

[EndlessCheng]

感觉可以添加一个小节，关于网络流的建模技巧和转换技巧。

[DBWGLX]

容量为0 减去 负的流量 == 正的剩余容量

[Yuzhiy05]

所有关于的图的示例中定义是否有问题？原示例中为vector<int> G[MAXN]不应该是vector<vector<int>> G吗

[Yuzhiy05]

我好像理解错了