二部マッチングでTLEに苦しんだ話

opencupで二部マッチングを使う問題があって、自分のライブラリが遅くてTLEにハマりました。
そのときに得た知見をまとめておきます。
頂点は合計200,000個、辺は200,000本、TLは3秒で、writerや他の人は400msくらいで通ってたらしい。

二部マッチングはdinicでやるとO(E√V)で解けることが知られているんですが、TLEでした。
少なくともライブラリをそのまま使うと超頂点を作って辺を張るので辺が合計400000本（+逆辺）になるっていうのもあり、定数倍が重いっぽい？
あと、ネット上で拾ったHopcroft-Karpも試してみたけどTLEでした。

蟻本には二部マッチング向けのシンプル版のアルゴリズムが書いてある（第二版だとp.197）のですが、この実装は速度的にやばいです。
そもそもforの中でmemsetを毎回やっていて、重いです。
これを工夫してused配列の初期化を高速化しても結構遅いです。

そこで、以下のようにusedを初期化せずに全始点を試してからusedを初期化するというのを更新がある限り繰り返すようにすると速くできるっぽいです。

struct match {
  vector<bool> used;
  vector<vector<int>> to;
  vector<int> p, q;
  int n, m;
  match(int n, int m):used(n),to(n),p(n,-1),q(m,-1),n(n),m(m){}
  void addEdge(int a, int b) { to[a].push_back(b);}
  bool dfs(int v) {
    if (used[v]) return false;
    used[v] = true;
    rep(i,to[v].size()) {
      int u = to[v][i];
      if (q[u] == -1 || dfs(q[u])) {
        q[u] = v;
        p[v] = u;
        return true;
      }
    }
    return false;
  }
  int solve() {
    int res = 0;
    bool upd = true;
    while (upd) {
      upd = false;
      rep(i,n) if (p[i] == -1 && dfs(i)) upd = true, ++res;
      if (upd) fill(used.begin(), used.end(), false);
    }
    return res;
  }
};

なんかこのアルゴリズムはKuhn's algorithmと呼ばれてるっぽいですが、調べても出どころがよく分からなかった。
参考にした人のコードでは辺とか頂点の順番をshuffleしてました。
このアルゴリズムの計算量はどうやって保証するんだろ。
追記：Kostromaさんが教えてくれました :D
少なくとも改善前のKuhnはO(VE)らしい。実用上は速いってやつかな。

おまけ

「used配列の初期化を高速化」は以下のようにやるとできます。

vector<int> used;
int ui;
~~~
if (used[v] == ui) return false;
used[v] = ui;
~~~
ui++; // fill(used.begin(), used.end(), false)と等価

おまけ２

DFSのかわりにBFSを使うと少し速くなった。
さらにそれを多始点BFSにして並列でやるともう少し速くなった。（元の２倍速くらい？）
もはやdinicにかなり近いのでO(E√V)とかだったりしないかな。
ちなみにdinicを二部マッチング向けにシンプルに実装してみたけどあんまり速くなかった。

追記2024-04-13：
これは何の理論的保証のない嘘解法の類であることに注意して下さい。
落とす気になれば撃墜ケースはちゃんとあるみたいです。
（頂点番号とか辺の順番とかを入力で工夫して）最初のループでの極大マッチングが図のようになると、その後左から多始点BFSしても、結局右側に到達する始点が１個とかになるのでループ毎に１しか解を更新できない、って感じかな。
辺の順番をシャッフルしたりするとマシにはなりそうだけど、まぁ怪しい。

struct BipartiteMatching {
  vector<int> pre, root;
  vector<vector<int>> to;
  vector<int> p, q;
  int n, m;
  BipartiteMatching(int n, int m):pre(n,-1),root(n,-1),to(n),p(n,-1),q(m,-1),n(n),m(m){}
  void add(int a, int b) { to[a].push_back(b);}
  int solve() {
    int res = 0;
    bool upd = true;
    while (upd) {
      upd = false;
      queue<int> s;
      for (int i = 0; i < n; ++i) {
        if (!~p[i]) {
          root[i] = i;
          s.push(i);
        }
      }
      while (!s.empty()) {
        int v = s.front(); s.pop();
        if (~p[root[v]]) continue;
        for (int i = 0; i < (int)to[v].size(); ++i) {
          int u = to[v][i];
          if (!~q[u]) {
            while (~u) {
              q[u] = v;
              swap(p[v],u);
              v = pre[v];
            }
            upd = true;
            ++res;
            break;
          }
          u = q[u];
          if (~pre[u]) continue;
          pre[u] = v; root[u] = root[v];
          s.push(u);
        }
      }
      if (upd) fill(pre.begin(),pre.end(),-1), fill(root.begin(),root.end(),-1);
    }
    return res;
  }
};