Travelling tours (SPOJ 387)

https://www.spoj.pl/problems/TOURS/

問題

頂点数nの有向グラフが与えられる。このグラフを閉路に分割したいのだが、全ての頂点を使って、なおかつ各閉路の使用する頂点は重なってはいけない。そのような分割の仕方で最小のものを求めよ。
1<=n<=200

解法

各頂点を2つに分割し、二部グラフを作成し最小費用流で最小重み完全マッチングを求める。最小重み完全マッチングの際に使用した辺により閉路が構成される。