2部マッチング

B. Valuable Paper ~Hopcroft–Karp algorithm~ 条件(capacity=1)付き2部マッチングでO(E sqrt(V))

Quiz https://codeforces.com/contest/1423/problem/B AC https://codeforces.com/contest/1423/submission/99738013 解説 editorialの通り、使う辺のコストの最大値を上げるほど最大マッチング=Nにしやすい(単調性)ので二分探索する しかし最大流を使っ…

AOJ 2251 - Merry Christmas ~DAG上の最小パス被覆 minimum path cover~

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251 できるだけ少ないサンタでプレゼントを配る問題 AC http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4866924#1 解説 L個の条件について、条件iを実行後、条件jに遷移できるなら…