AOJ 2828 - マトリョーシカ

問題
提出コード
解説ACです。マッチング、難しいですね…

解法

元の問題について、体積の最小値ではなく、見えているマトリョーシカの個数を求める問題は、
最小パス被覆問題そのものになっています。これは二部グラフの最大マッチングに帰着させることができます。
sourse、sinkと、マトリョーシカそれぞれに対してin,outの2つずつ頂点を用意してあげます。
あとは、sourseから個のout、個のinからsinkに加え、マトリョーシカがをしまうことができる場合に、マトリョーシカのoutからのinに向け、それぞれ容量1の辺を張ればよいです。
体積の最小値の場合は、これを応用して重み付き二部マッチングによって解くことができます。
容量は全てそのままで、のoutからのinに向けて張った辺について、コストをの体積について符号を反転させた値とすることで、辺をカットする行為がの体積だけ得をすることに結び付けられます。
その他の部分でコストがかかることはないため0にしてしまえばよいです。
辺について一番異なるのは、最小費用流の場合、容量を流すと指定しなければならない部分で、最終的に一番外側になるマトリョーシカ分もフローを流さなければなりません。これは、それぞれのマトリョーシカのoutから、直接sinkにコスト0、容量1の辺を張ることで表現できます。
あとは、だけ流すのにかかるコストの最小を求め、その-1倍したものを、体積の合計から引くことで、最終的に一番外側になっているマトリョーシカの体積が求まります。
自分は、-1倍して解かずに、これを用いて解きました。2つのマトリョーシカを結ぶ辺については、、outからsinkに向けてはのコストに直します。すると、
が最終的に得をする分の体積になります。