回答編集履歴
3
文言修正
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
何らかの参考になるかもしれないので，「全てのノードを通る閉路のうち重みの総和が最小のもの」を求める問題なのだとして，私が解いてみた（つもりの）コードを示してみます．
|
|
3
3
|
（…とは言え，貪欲法である以上，本当に「最小」が見つかる保証はないわけですが）
|
|
4
4
|
|
|
5
|
-
* ファイルからデータを読むところと，辺のデータをソートするところは本題ではないので含めていません．（：データ
|
|
5
|
+
* ファイルからデータを読むところと，辺のデータをソートするところは本題ではないので含めていません．（：ソート済みデータを定数として実装しています）
|
|
6
6
|
* 貪欲法の部分は再帰関数になっていますが，その処理中に使うデータ（`NodeDeg[]`, `EdgeUsed[]`）は外部変数にしてあります（その方が読みやすいと思うので）．
|
|
7
7
|
* また，コードは C++ になっていますが，「C言語っぽく」書いたつもりですので，そのあたりは大丈夫かと．
|
|
8
8
|
|
2
結果を追加
test
CHANGED
|
@@ -134,3 +134,19 @@
|
|
|
134
134
|
return 0;
|
|
135
135
|
}
|
|
136
136
|
```
|
|
137
|
+
|
|
138
|
+
↑のコードを動作させた結果の表示：
|
|
139
|
+
```
|
|
140
|
+
Try to adopt Edge 1 - 3
|
|
141
|
+
Try to adopt Edge 0 - 3
|
|
142
|
+
Try to adopt Edge 0 - 1
|
|
143
|
+
Try to adopt Edge 2 - 4
|
|
144
|
+
Reject Edge 2 - 4
|
|
145
|
+
Reject Edge 0 - 1
|
|
146
|
+
Try to adopt Edge 1 - 4
|
|
147
|
+
Try to adopt Edge 0 - 2
|
|
148
|
+
Try to adopt Edge 2 - 4
|
|
149
|
+
---Result---
|
|
150
|
+
Path : 1 -> 3 -> 0 -> 2 -> 4 -> 1
|
|
151
|
+
TotalCost = 3311.100000
|
|
152
|
+
```
|
1
念のための追記
test
CHANGED
|
@@ -1,5 +1,6 @@
|
|
|
1
1
|
**「既存のコードを修正してくれ」という話への回答とはなりません** が，
|
|
2
2
|
何らかの参考になるかもしれないので，「全てのノードを通る閉路のうち重みの総和が最小のもの」を求める問題なのだとして，私が解いてみた（つもりの）コードを示してみます．
|
|
3
|
+
（…とは言え，貪欲法である以上，本当に「最小」が見つかる保証はないわけですが）
|
|
3
4
|
|
|
4
5
|
* ファイルからデータを読むところと，辺のデータをソートするところは本題ではないので含めていません．（：データは 定数/変数 として実装しています）
|
|
5
6
|
* 貪欲法の部分は再帰関数になっていますが，その処理中に使うデータ（`NodeDeg[]`, `EdgeUsed[]`）は外部変数にしてあります（その方が読みやすいと思うので）．
|