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

わんくま同盟

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

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


(過去ログ 98 を表示中)
■58201 / )  Re[6]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (6回)-(2011/03/28(Mon) 22:20:53)
No58197 (shu さん) に返信
> ■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 -