C# と VB.NET の質問掲示板

わんくま同盟

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト


(過去ログ 98 を表示中)
■58197 / )  Re[5]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ shu (572回)-(2011/03/28(Mon) 21:31:19)
No58194 (堀江伸一 さん) に返信

> 余談ですが、この問題m=2の場合は簡単です。
> 発電所をh,電気を流したい地点をm1,m2とします。
> 地点iとjを結ぶ最短距離をmap[i][j]と表現する時、map[m1][k]+map[m2][k]+map[h][k]が最小となる地点kを電線の分岐点とすればいいだけです。

賢くない方法ですが、抽出点i1〜imについてそれぞれの2点の最短経路を求めるとm点のグラフと同等になるので求められるんじゃないかな?



返信 編集キー/


管理者用

- Child Tree -