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

編集履歴

質問編集履歴

8

校正

2017/04/23 01:48

投稿

gyro16
gyro16

スコア89

title CHANGED
File without changes
body CHANGED
@@ -16,46 +16,6 @@
16
16
 
17
17
  全頂点をめぐる回路・全域木の最小の経路・全域木をもとめる
18
18
 
19
- 期待したい流れ
20
- ↓
21
- seekMin()
22
- leng[0][3] 1
23
- min = leng[x][y];
24
- xx = x;
25
- yy = y;
26
- reach[xx] = 0;
27
- reach[yy] = leng[x][y];
28
- reach[3] = 1;
29
- x = yy;
30
- y = xx continue;
31
- leng[3][0]スキップ
32
- leng[3][2] 1
33
- xx = x;
34
- yy = y;
35
- reach[yy] = leng[x][y];
36
- reach[2] = 1;
37
- x = yy;
38
- y = xx continue;
39
- leng[2][3]スキップ
40
- leng[2][4] 1
41
- xx = x;
42
- yy = y;
43
- reach[yy] = leng[x][y];
44
- reach[4] = 1;
45
-
46
-
47
-
48
-
49
-
50
- total = 0;
51
- for(int i = 0; i < n; i++)
52
- total += reach[i];
53
-
54
- ↑
55
- この流れを変数を利用して記述したいです。
56
- アルゴリズム書き直しでもよいです。
57
-
58
-
59
19
  ###発生している問題・エラーメッセージ
60
20
 
61
21
  この辺りの処理の流れがわかりません

7

思考中

2017/04/23 01:48

投稿

gyro16
gyro16

スコア89

title CHANGED
File without changes
body CHANGED
@@ -18,59 +18,35 @@
18
18
 
19
19
  期待したい流れ
20
20
  ↓
21
- min()
21
+ seekMin()
22
- min = MAX_VALUE;
23
- leng[0][3] 1；
22
+ leng[0][3] 1
24
23
  min = leng[x][y];
25
24
  xx = x;
26
25
  yy = y;
27
- reach[yy] = min;
26
+ reach[xx] = 0;
27
+ reach[yy] = leng[x][y];
28
28
  reach[3] = 1;
29
- min()
30
29
  x = yy;
31
- min = MAX_VALUE;
32
30
  y = xx continue;
33
- leng[3][0]をスキップして、
31
+ leng[3][0]スキップ
34
- leng[3][1] 1;
32
+ leng[3][2] 1
35
- min = leng[x][y];
36
33
  xx = x;
37
34
  yy = y;
38
- reach[yy] = min;
39
- reach[1] = 1;
40
- min()
41
- x = yy;
42
- min = MAX_VALUE;
43
- y = xx continue;
44
- leng[1][0] 2;
45
- min = leng[x][y];
35
+ reach[yy] = leng[x][y];
46
- xx = x;
47
- yy = y;
48
- reach[yy] = min;
49
- reach[0] = 2;
50
-
51
- どうやって下につなぐか？
52
- ここの下へつなげる
53
- min2()
54
- min = MAX_VALUE;
55
- leng[4][2] 1;
56
- min = length[x][y];
57
- xx = x;
58
- yy = y;
59
- reach[yy] = min2;
60
36
  reach[2] = 1;
61
- min2()
62
37
  x = yy;
63
- min = MAX_VALUE;
64
38
  y = xx continue;
39
+ leng[2][3]スキップ
65
- leng[2][3] 1;
40
+ leng[2][4] 1
66
- min2 = leng[x][y];
67
41
  xx = x;
68
42
  yy = y;
69
- for(int i = 0; i < reach.length; i++)
70
- if(reach[i] == -1)
43
+ reach[yy] = leng[x][y];
71
- reach[3] != -1；終了
44
+ reach[4] = 1;
72
45
 
73
46
 
47
+
48
+
49
+
74
50
  total = 0;
75
51
  for(int i = 0; i < n; i++)
76
52
  total += reach[i];

6

思考中

2017/04/23 00:31

投稿

gyro16
gyro16

スコア89

title CHANGED
File without changes
body CHANGED
@@ -51,9 +51,9 @@
51
51
  どうやって下につなぐか？
52
52
  ここの下へつなげる
53
53
  min2()
54
- min2 = MAX_VALUE;
54
+ min = MAX_VALUE;
55
55
  leng[4][2] 1;
56
- min2 = length[x][y];
56
+ min = length[x][y];
57
57
  xx = x;
58
58
  yy = y;
59
59
  reach[yy] = min2;

5

思考中

2017/04/22 10:57

投稿

gyro16
gyro16

スコア89

title CHANGED
File without changes
body CHANGED
@@ -66,7 +66,8 @@
66
66
  min2 = leng[x][y];
67
67
  xx = x;
68
68
  yy = y;
69
+ for(int i = 0; i < reach.length; i++)
69
- while(reach[yy] != -1)
70
+ if(reach[i] == -1)
70
71
  reach[3] != -1；終了
71
72
 
72
73
 

4

思考中

2017/04/22 10:30

投稿

gyro16
gyro16

スコア89

title CHANGED
File without changes
body CHANGED
@@ -18,23 +18,58 @@
18
18
 
19
19
  期待したい流れ
20
20
  ↓
21
-
21
+ min()
22
+ min = MAX_VALUE;
22
23
  leng[0][3] 1；
24
+ min = leng[x][y];
25
+ xx = x;
26
+ yy = y;
23
- reach[0] = 0;
27
+ reach[yy] = min;
24
28
  reach[3] = 1;
29
+ min()
30
+ x = yy;
31
+ min = MAX_VALUE;
32
+ y = xx continue;
25
33
  leng[3][0]をスキップして、
26
34
  leng[3][1] 1;
35
+ min = leng[x][y];
36
+ xx = x;
37
+ yy = y;
38
+ reach[yy] = min;
27
39
  reach[1] = 1;
40
+ min()
41
+ x = yy;
42
+ min = MAX_VALUE;
43
+ y = xx continue;
28
44
  leng[1][0] 2;
45
+ min = leng[x][y];
46
+ xx = x;
47
+ yy = y;
48
+ reach[yy] = min;
29
49
  reach[0] = 2;
30
50
 
31
51
  どうやって下につなぐか？
32
52
  ここの下へつなげる
53
+ min2()
54
+ min2 = MAX_VALUE;
33
55
  leng[4][2] 1;
56
+ min2 = length[x][y];
57
+ xx = x;
58
+ yy = y;
59
+ reach[yy] = min2;
34
60
  reach[2] = 1;
61
+ min2()
62
+ x = yy;
63
+ min = MAX_VALUE;
64
+ y = xx continue;
35
65
  leng[2][3] 1;
66
+ min2 = leng[x][y];
67
+ xx = x;
68
+ yy = y;
69
+ while(reach[yy] != -1)
36
70
  reach[3] != -1；終了
37
71
 
72
+
38
73
  total = 0;
39
74
  for(int i = 0; i < n; i++)
40
75
  total += reach[i];

3

思考中

2017/04/22 06:49

投稿

gyro16
gyro16

スコア89

title CHANGED
File without changes
body CHANGED
@@ -19,7 +19,7 @@
19
19
  期待したい流れ
20
20
  ↓
21
21
 
22
- leng[0][3] 1
22
+ leng[0][3] 1；
23
23
  reach[0] = 0;
24
24
  reach[3] = 1;
25
25
  leng[3][0]をスキップして、
@@ -33,7 +33,7 @@
33
33
  leng[4][2] 1;
34
34
  reach[2] = 1;
35
35
  leng[2][3] 1;
36
- reach[3] = 1;
36
+ reach[3] != -1；終了
37
37
 
38
38
  total = 0;
39
39
  for(int i = 0; i < n; i++)

2

思考中

2017/04/22 06:05

投稿

gyro16
gyro16

スコア89

title CHANGED
File without changes
body CHANGED
@@ -28,6 +28,7 @@
28
28
  leng[1][0] 2;
29
29
  reach[0] = 2;
30
30
 
31
+ どうやって下につなぐか？
31
32
  ここの下へつなげる
32
33
  leng[4][2] 1;
33
34
  reach[2] = 1;
@@ -39,7 +40,10 @@
39
40
  total += reach[i];
40
41
 
41
42
  ↑
43
+ この流れを変数を利用して記述したいです。
44
+ アルゴリズム書き直しでもよいです。
42
45
 
46
+
43
47
  ###発生している問題・エラーメッセージ
44
48
 
45
49
  この辺りの処理の流れがわかりません

1

思考中

2017/04/22 06:01

投稿

gyro16
gyro16

スコア89

title CHANGED
File without changes
body CHANGED
@@ -16,7 +16,30 @@
16
16
 
17
17
  全頂点をめぐる回路・全域木の最小の経路・全域木をもとめる
18
18
 
19
+ 期待したい流れ
20
+ ↓
19
21
 
22
+ leng[0][3] 1
23
+ reach[0] = 0;
24
+ reach[3] = 1;
25
+ leng[3][0]をスキップして、
26
+ leng[3][1] 1;
27
+ reach[1] = 1;
28
+ leng[1][0] 2;
29
+ reach[0] = 2;
30
+
31
+ ここの下へつなげる
32
+ leng[4][2] 1;
33
+ reach[2] = 1;
34
+ leng[2][3] 1;
35
+ reach[3] = 1;
36
+
37
+ total = 0;
38
+ for(int i = 0; i < n; i++)
39
+ total += reach[i];
40
+
41
+ ↑
42
+
20
43
  ###発生している問題・エラーメッセージ
21
44
 
22
45
  この辺りの処理の流れがわかりません