[問題案]General Matching(general_matching)

[yosupo06]

制約

// O(V^3), O(VE), O(VE log V)?

• 1 <= N <= 300
• 1 <= M <= N(N - 1) / 2

// O(E sqrt V)

• 1 <= N <= 100,000
• 1 <= M <= 100,000

[yosupo06]

計算量によって実装量がかわり過ぎるのをどうするか

[yosupo06]

https://github.com/yosupo06/library-checker-problems/issues/3#issuecomment-532303364

[yosupo06]

O(V^3)でとりあえず作る

[yosupo06]

https://judge.yosupo.jp/submission/987 嘘解法が通っている(ランダムケースだけだからね…)

[potetisensei]

強い（らしい）乱択が落ちるケースが試行回数低いと落ちるケースが入ってる（らしい）ジャッジ:

• http://acm.timus.ru/problem.aspx?space=1&num=1099
• http://uoj.ac/problem/79 後者は試行回数チューニングしたら通っちゃったけども

[yosupo06]

激 Love

[potetisensei]

上のも含めて大体ソースはCFです。 http://acm.math.spbu.ru/~sk1/courses/1718f_au2/conspect/conspect.pdf ↑General Matchingの乱択について書かれていて、乱択で増加路を見つけられる確率が頂点数の指数の逆数オーダー（？）であるようなグラフがあると書かれているが、具体的な例が載っていないため何もわからない（5ページ目、最後） 乱択 http://uoj.ac/submission/233938

[yosupo06]

ありがとうございます！　

[yosupo06]

(ところでロシア語なんですが…>＜)

[potetisensei]

いや俺も読めないけど 元のCFの記事貼ったほうがいいですか、割とネタバレになり得るので貼ってなかったんですが

[maspypy]

テストケース追加の作業者募集状態っぽい