回答編集履歴
1
加筆
answer
CHANGED
|
@@ -1,2 +1,7 @@
|
|
|
1
1
|
主要じゃない都市のどれを使うかを決めれば最小スパニングツリーの問題になります
|
|
2
|
-
主要じゃない都市の組み合わせすべてについてこの問題を解けば全体の最小値が出ます
|
|
2
|
+
主要じゃない都市の組み合わせすべてについてこの問題を解けば全体の最小値が出ます
|
|
3
|
+
|
|
4
|
+
---
|
|
5
|
+
追記：
|
|
6
|
+
最小スパニングツリーの問題は、全部のノードをつないだ時の最小コストを求める問題。今回の問題で違うのが、つなげなきゃいけないのは一部のノードだけで、残りはつなげても繋げなくてもどちらでもいいというところです。
|
|
7
|
+
そこで、どちらでもいいノードをつなげるノードとつなげないノードに分ける方法を全パターン試すことにします。あらかじめ分けられてさえいれば、つなげるノードだけ考えて最小スパニングツリーの問題として解くことができるので、学習した範囲の問題。それをすべてのノードの組み合わせについて繰り返し解くだけ。すべての分け方のなかで最もコストの少なかったものが今回の問題の解です。
|