Peach Blossom Spring (UVa Live Archive Asia Beigin 2011)
問題
頂点数n、枝数mのグラフGが与えられる。グラフの辺は最初壊れていて、それを直すのにコストwiかかる。1番目の頂点からk番目の頂点とn-k+1番目の頂点からn番目の頂点でマッチングを取れるように辺を直したい。必要なコストの最小値を求めよ。
4<=n<=50
0<=m<=1000
1<=k<=min(n/2,5)
解法
最小シュタイナー森問題になる。ただしマッチングを取らなければならないので少し修正する必要がある。そこでk以下の頂点の数とn-k+1以上の頂点の数が一致するときに、ひげをのばすコスト*1を0とすると求める物が得られる。
*1:シュタイナー木を求める際に「ターミナルの頂点集合+ある頂点」でDPするがそのある頂点から別の頂点へ経路伸ばすコスト
