(o_o)

ブログ。

AOJ2352 Divisor

異なる a, b について,a が b の倍数になるときに a から b に辺を張るような N 頂点のグラフを考える.このグラフは推移的グラフであるので,最大独立集合 = 最小パス被覆 である (Dilworth の定理).DAG の最小パス被覆は二部グラフの最大マッチングで解ける.