一般最大マッチング / 一般最大重み付きマッチングの実装

一般最大マッチングと一般最大重み付きマッチングの実装例です。

一般最大マッチング

$O(nm \log_{\max\{2, 1 + m/n\}} n)$ の実装

改善箇所
  • L5 での更新を UnionFind の find のような形で遅延させると、計算量が $O(n^3)$ から $O(nm \log{n})$ に改善されます。
  • augmenting path が見つからなかった場合に E7 の処理を飛ばす(頂点の Label を保つ)と、今後 augmenting path 上の頂点になり得ない頂点の探索をカットでき、実用上早くなることが多いです。
実行例
  • 一般 はランダムグラフ、二部 は $|V|/2$ ずつで分けたランダムグラフ
  • 辺の生成は自己ループ・多重辺込みで一様ランダム
  • 実行時間の単位は秒

$V$ $E$ 一般グラフ 二部グラフ
$10^5$ $2 \cdot 10^5$ 0.159 0.105
$10^5$ $3 \cdot 10^5$ 0.124 0.072
$10^6$ $2 \cdot 10^6$ 9.93 13.8
$10^6$ $3 \cdot 10^6$ 6.25 6.41
$10^7$ $2 \cdot 10^7$ 237 938
$10^7$ $3 \cdot 10^7$ 112 397

$O(\sqrt{n}m \log_{\max\{2, 1 + m/n\}} n)$ の実装

備考
  • Micali and Vazirani の $O(\sqrt{n} m)$ よりは、定数倍的に少し遅い (?)
  • ランダムなグラフでは、$O(nm \log n)$ のものとは少し挙動が違って、$|E| \approx 1.4 |V|$ 付近が苦手。
実行例

$V$ $E$ 一般グラフ 二部グラフ
$10^5$ $2 \cdot 10^5$ 0.134 0.125
$10^5$ $3 \cdot 10^5$ 0.136 0.095
$10^6$ $2 \cdot 10^6$ 2.87 2.94
$10^6$ $3 \cdot 10^6$ 1.92 2.19
$10^7$ $2 \cdot 10^7$ 53.2 43.4
$10^7$ $3 \cdot 10^7$ 30.7 33.8

入力に対する制約

  • 各頂点は $1$-indexed です。
  • 自己ループ・多重辺が存在しても動作します。

Verify 用の問題

一般最大重み付きマッチング

$O(n^2m)$ の実装

ソースコード

(少し無駄な処理が多い…)

参考文献
  • Combinatorial Optimization: Algorithms and Complexity, pp.255-266.
  • Guido Schäfer: Master's thesis p.33, Algorithm 1.6.3

$O(n^3)$ の実装

ソースコード

(少し無駄な処理が多い…)

$O(nm \log{n})$ の実装

3 つの中では、この実装が一番高速に動作します。

入力に対する制約

  • 各頂点は $1$-indexed です。
  • 各辺の重み $w$ は非負整数かつ inf / 2 未満($< 2^{29}$, $< 2^{61}$ など)です。
  • 自己ループ・多重辺が存在しても動作します。

verify 用の問題

乱択解法

短いコードで書け、正しい答えを高確率で返せる(指数時間の)乱択解法があるようです。

弱めの例題では、上の提出のように $n = 400$ でも短時間で解いています。
ただ、強めの例題では $n \approx 60$ でも 1 秒ぐらいかかるので、万能というわけではないようです。