[問題案] Minimum Steiner Tree

[SSRS-cp]

問題名: Minimum Steiner Tree 資料: https://www.slideshare.net/wata_orz/ss-12131479 p50

問題

$N$ 頂点 $M$ 辺の重み付き無向グラフ $G$ が与えられる。$i$ ($0 \leq i \lt M$) 番目の辺は頂点 $U_i$ と $V_i$ を結び、重みは $W_i$ である。

$V(G)$ の部分集合 $S={X_0, X_1, \dots, X_{K-1}}$ が与えられるので、$G$ の部分グラフで $K$ のどの $2$ 頂点間も連結であるようなもののうち、辺重みの総和が最小のものを求めよ。

入力

N M
U_0 V_0 W_0
U_1 V_1 W_1
...
U_{M-1} V_{M-1} W_{M-1}
K
X_0 X_1 ... X_{K-1}

出力

最小値が $ans$ で、選ぶ部分グラフの辺が $G$ の $i_0, i_1, \dots, i_{K-2}$ のとき、以下のように出力

ans
i_0 i_1 ... i_{K-2}

メモ

・グラフは連結とするか ・K=0 を入れるか ・制約をどれくらいにするか (要調整)

[maspypy]

仮に案を出しておきます。

• グラフは連結
• $K>0$
• 制約： $K\leq 12, N\leq 100, M\leq 1000$

[maspypy]

上は $O(3^kn+2^km\log m)$ の想定です（修正）。 yukicoder に $O(2^{n-k} poly(n))$ と使い分ける問題があったりしますが、とりあえず 3^k のやつでいいかな？

[NachiaVivias]

上は $O(3^kn + 2^k m)$ の想定です。

辺重み付きだったら、最短経路問題の計算量が変わって $O(3^k n + 2^k m\log m)$ （例）になりませんか？（そうだとして制約は変わらないと思いますが）

[maspypy]

作業者募集です。