1422

閉路のない有向グラフが与えられる。すべてのノードは最初は印がついていない状態とする。任意のノードを開始点として印をつける。印をつけたノードから隣接する印のついていないノードへの移動が可能で、そのノードには印がつく。すべてのノードに印をつけるまでに、この操作が必要な最小の回数を答えよ、という問題。

要はノード間遷移の回数を最大化する問題。あるノードから移動するときは高々一つのそれを開始点とする枝しか選択できず、あるノードへ到達するのは高々一つのそれを終了点とする枝である。開始点を左点、終了点を右点とする二部グラフを作れば、その最大マッチング数を求めることに等しいので、最大流を求めればおしまい。