二部マッチングで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)と等価

おまけ2

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

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;
  }
};