teratail
回答率
85.47%
質問するログイン新規登録
トップに関する質問最小の回路・全域木をもとめるアルゴリズムの流れがわからない部分を意訳していただけませんか？

編集履歴

質問編集履歴

8

校正

2017/04/23 01:48

投稿

gyro16
gyro16

スコア89

test CHANGED
File without changes
test CHANGED
@@ -34,86 +34,6 @@
34
34
 
35
35
 
36
36
 
37
- 期待したい流れ
38
-
39
- ↓
40
-
41
- seekMin()
42
-
43
- leng[0][3] 1
44
-
45
- min = leng[x][y];
46
-
47
- xx = x;
48
-
49
- yy = y;
50
-
51
- reach[xx] = 0;
52
-
53
- reach[yy] = leng[x][y];
54
-
55
- reach[3] = 1;
56
-
57
- x = yy;
58
-
59
- y = xx continue;
60
-
61
- leng[3][0]スキップ
62
-
63
- leng[3][2] 1
64
-
65
- xx = x;
66
-
67
- yy = y;
68
-
69
- reach[yy] = leng[x][y];
70
-
71
- reach[2] = 1;
72
-
73
- x = yy;
74
-
75
- y = xx continue;
76
-
77
- leng[2][3]スキップ
78
-
79
- leng[2][4] 1
80
-
81
- xx = x;
82
-
83
- yy = y;
84
-
85
- reach[yy] = leng[x][y];
86
-
87
- reach[4] = 1;
88
-
89
-
90
-
91
-
92
-
93
-
94
-
95
-
96
-
97
-
98
-
99
- total = 0;
100
-
101
- for(int i = 0; i < n; i++)
102
-
103
- total += reach[i];
104
-
105
-
106
-
107
- ↑
108
-
109
- この流れを変数を利用して記述したいです。
110
-
111
- アルゴリズム書き直しでもよいです。
112
-
113
-
114
-
115
-
116
-
117
37
  ###発生している問題・エラーメッセージ
118
38
 
119
39
 

7

思考中

2017/04/23 01:48

投稿

gyro16
gyro16

スコア89

test CHANGED
File without changes
test CHANGED
@@ -38,11 +38,9 @@
38
38
 
39
39
  ↓
40
40
 
41
- min()
41
+ seekMin()
42
-
43
- min = MAX_VALUE;
42
+
44
-
45
- leng[0][3] 1；
43
+ leng[0][3] 1
46
44
 
47
45
  min = leng[x][y];
48
46
 
@@ -50,95 +48,49 @@
50
48
 
51
49
  yy = y;
52
50
 
53
- reach[yy] = min;
51
+ reach[xx] = 0;
52
+
53
+ reach[yy] = leng[x][y];
54
54
 
55
55
  reach[3] = 1;
56
56
 
57
- min()
58
-
59
57
  x = yy;
60
58
 
61
- min = MAX_VALUE;
62
-
63
59
  y = xx continue;
64
60
 
65
- leng[3][0]をスキップして、
61
+ leng[3][0]スキップ
66
-
62
+
67
- leng[3][1] 1;
63
+ leng[3][2] 1
68
-
69
- min = leng[x][y];
70
64
 
71
65
  xx = x;
72
66
 
73
67
  yy = y;
74
68
 
75
- reach[yy] = min;
69
+ reach[yy] = leng[x][y];
76
-
70
+
77
- reach[1] = 1;
71
+ reach[2] = 1;
78
-
79
- min()
80
72
 
81
73
  x = yy;
82
74
 
83
- min = MAX_VALUE;
84
-
85
75
  y = xx continue;
86
76
 
77
+ leng[2][3]スキップ
78
+
87
- leng[1][0] 2;
79
+ leng[2][4] 1
88
-
89
- min = leng[x][y];
90
80
 
91
81
  xx = x;
92
82
 
93
83
  yy = y;
94
84
 
95
- reach[yy] = min;
96
-
97
- reach[0] = 2;
98
-
99
-
100
-
101
- どうやって下につなぐか？
102
-
103
- ここの下へつなげる
104
-
105
- min2()
106
-
107
- min = MAX_VALUE;
108
-
109
- leng[4][2] 1;
110
-
111
- min = length[x][y];
112
-
113
- xx = x;
114
-
115
- yy = y;
116
-
117
- reach[yy] = min2;
85
+ reach[yy] = leng[x][y];
118
-
86
+
119
- reach[2] = 1;
87
+ reach[4] = 1;
120
-
121
- min2()
88
+
122
-
123
- x = yy;
89
+
124
-
125
- min = MAX_VALUE;
90
+
126
-
127
- y = xx continue;
91
+
128
-
129
- leng[2][3] 1;
92
+
130
-
131
- min2 = leng[x][y];
93
+
132
-
133
- xx = x;
134
-
135
- yy = y;
136
-
137
- for(int i = 0; i < reach.length; i++)
138
-
139
- if(reach[i] == -1)
140
-
141
- reach[3] != -1；終了
142
94
 
143
95
 
144
96
 

6

思考中

2017/04/23 00:31

投稿

gyro16
gyro16

スコア89

test CHANGED
File without changes
test CHANGED
@@ -104,11 +104,11 @@
104
104
 
105
105
  min2()
106
106
 
107
- min2 = MAX_VALUE;
107
+ min = MAX_VALUE;
108
108
 
109
109
  leng[4][2] 1;
110
110
 
111
- min2 = length[x][y];
111
+ min = length[x][y];
112
112
 
113
113
  xx = x;
114
114
 

5

思考中

2017/04/22 10:57

投稿

gyro16
gyro16

スコア89

test CHANGED
File without changes
test CHANGED
@@ -134,7 +134,9 @@
134
134
 
135
135
  yy = y;
136
136
 
137
+ for(int i = 0; i < reach.length; i++)
138
+
137
- while(reach[yy] != -1)
139
+ if(reach[i] == -1)
138
140
 
139
141
  reach[3] != -1；終了
140
142
 

4

思考中

2017/04/22 10:30

投稿

gyro16
gyro16

スコア89

test CHANGED
File without changes
test CHANGED
@@ -38,22 +38,62 @@
38
38
 
39
39
  ↓
40
40
 
41
-
41
+ min()
42
+
43
+ min = MAX_VALUE;
42
44
 
43
45
  leng[0][3] 1；
44
46
 
47
+ min = leng[x][y];
48
+
49
+ xx = x;
50
+
51
+ yy = y;
52
+
45
- reach[0] = 0;
53
+ reach[yy] = min;
46
54
 
47
55
  reach[3] = 1;
48
56
 
57
+ min()
58
+
59
+ x = yy;
60
+
61
+ min = MAX_VALUE;
62
+
63
+ y = xx continue;
64
+
49
65
  leng[3][0]をスキップして、
50
66
 
51
67
  leng[3][1] 1;
52
68
 
69
+ min = leng[x][y];
70
+
71
+ xx = x;
72
+
73
+ yy = y;
74
+
75
+ reach[yy] = min;
76
+
53
77
  reach[1] = 1;
54
78
 
79
+ min()
80
+
81
+ x = yy;
82
+
83
+ min = MAX_VALUE;
84
+
85
+ y = xx continue;
86
+
55
87
  leng[1][0] 2;
56
88
 
89
+ min = leng[x][y];
90
+
91
+ xx = x;
92
+
93
+ yy = y;
94
+
95
+ reach[yy] = min;
96
+
57
97
  reach[0] = 2;
58
98
 
59
99
 
@@ -62,16 +102,46 @@
62
102
 
63
103
  ここの下へつなげる
64
104
 
105
+ min2()
106
+
107
+ min2 = MAX_VALUE;
108
+
65
109
  leng[4][2] 1;
66
110
 
111
+ min2 = length[x][y];
112
+
113
+ xx = x;
114
+
115
+ yy = y;
116
+
117
+ reach[yy] = min2;
118
+
67
119
  reach[2] = 1;
68
120
 
121
+ min2()
122
+
123
+ x = yy;
124
+
125
+ min = MAX_VALUE;
126
+
127
+ y = xx continue;
128
+
69
129
  leng[2][3] 1;
70
130
 
131
+ min2 = leng[x][y];
132
+
133
+ xx = x;
134
+
135
+ yy = y;
136
+
137
+ while(reach[yy] != -1)
138
+
71
139
  reach[3] != -1；終了
72
140
 
73
141
 
74
142
 
143
+
144
+
75
145
  total = 0;
76
146
 
77
147
  for(int i = 0; i < n; i++)

3

思考中

2017/04/22 06:49

投稿

gyro16
gyro16

スコア89

test CHANGED
File without changes
test CHANGED
@@ -40,7 +40,7 @@
40
40
 
41
41
 
42
42
 
43
- leng[0][3] 1
43
+ leng[0][3] 1；
44
44
 
45
45
  reach[0] = 0;
46
46
 
@@ -68,7 +68,7 @@
68
68
 
69
69
  leng[2][3] 1;
70
70
 
71
- reach[3] = 1;
71
+ reach[3] != -1；終了
72
72
 
73
73
 
74
74
 

2

思考中

2017/04/22 06:05

投稿

gyro16
gyro16

スコア89

test CHANGED
File without changes
test CHANGED
@@ -58,6 +58,8 @@
58
58
 
59
59
 
60
60
 
61
+ どうやって下につなぐか？
62
+
61
63
  ここの下へつなげる
62
64
 
63
65
  leng[4][2] 1;
@@ -80,6 +82,12 @@
80
82
 
81
83
  ↑
82
84
 
85
+ この流れを変数を利用して記述したいです。
86
+
87
+ アルゴリズム書き直しでもよいです。
88
+
89
+
90
+
83
91
 
84
92
 
85
93
  ###発生している問題・エラーメッセージ

1

思考中

2017/04/22 06:01

投稿

gyro16
gyro16

スコア89

test CHANGED
File without changes
test CHANGED
@@ -34,6 +34,52 @@
34
34
 
35
35
 
36
36
 
37
+ 期待したい流れ
38
+
39
+ ↓
40
+
41
+
42
+
43
+ leng[0][3] 1
44
+
45
+ reach[0] = 0;
46
+
47
+ reach[3] = 1;
48
+
49
+ leng[3][0]をスキップして、
50
+
51
+ leng[3][1] 1;
52
+
53
+ reach[1] = 1;
54
+
55
+ leng[1][0] 2;
56
+
57
+ reach[0] = 2;
58
+
59
+
60
+
61
+ ここの下へつなげる
62
+
63
+ leng[4][2] 1;
64
+
65
+ reach[2] = 1;
66
+
67
+ leng[2][3] 1;
68
+
69
+ reach[3] = 1;
70
+
71
+
72
+
73
+ total = 0;
74
+
75
+ for(int i = 0; i < n; i++)
76
+
77
+ total += reach[i];
78
+
79
+
80
+
81
+ ↑
82
+
37
83
 
38
84
 
39
85
  ###発生している問題・エラーメッセージ