二分图最大匹配

[sshwy]

https://oi-wiki.org/topic/graph-matching/bigraph-match/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[Little-Eye]

优先从左边集合的未匹配点找增广路的话，就只需要以左边集合的未匹配点为起点找了。假如以左边集合的未匹配点为起点找不到增广路，此时以右边集合的未匹配点为起点找找到了一条增广路，由于增广路的性质决定了它的长度一定为奇数，那么说明这条增广路的终点一定在左边，这和前面的假设相违背。

[Lotuses-robot]

请问为什么没有提到 $O(m\sqrt{n})$ 的 Hopcroft-Karp 算法呢？本文中要做到 $O(m\sqrt{n})$ 也只能通过转换成最大流模型。

[ShelpAm]

求增广路代码的注释

[ShelpAm]

请问这段代码中，g.resize(n);的目的是什么？我把这行删掉，代码仍然是AC的。

  augment_path(int _n, int _m) : n(_n), m(_m) {
    assert(0 <= n && 0 <= m);
    pa = vector<int>(n, -1);
    pb = vector<int>(m, -1);
    vis = vector<int>(n);
    g.resize(n);
    res = 0;
    dfn = 0;
  }

[ShelpAm]

没问题了，我的代码和这个不一样