2013
12-30

# 哈密顿绕行世界问题

2 5 20
1 3 12
2 4 10
3 5 8
1 4 6
5 7 19
6 8 17
4 7 9
8 10 16
3 9 11
10 12 15
2 11 13
12 14 20
13 15 18
11 14 16
9 15 17
7 16 18
14 17 19
6 18 20
1 13 19
5
0

1:  5 1 2 3 4 8 7 17 18 14 15 16 9 10 11 12 13 20 19 6 5
2:  5 1 2 3 4 8 9 10 11 12 13 20 19 18 14 15 16 17 7 6 5
3:  5 1 2 3 10 9 16 17 18 14 15 11 12 13 20 19 6 7 8 4 5
4:  5 1 2 3 10 11 12 13 20 19 6 7 17 18 14 15 16 9 8 4 5
5:  5 1 2 12 11 10 3 4 8 9 16 15 14 13 20 19 18 17 7 6 5
6:  5 1 2 12 11 15 14 13 20 19 18 17 16 9 10 3 4 8 7 6 5
7:  5 1 2 12 11 15 16 9 10 3 4 8 7 17 18 14 13 20 19 6 5
8:  5 1 2 12 11 15 16 17 18 14 13 20 19 6 7 8 9 10 3 4 5
9:  5 1 2 12 13 20 19 6 7 8 9 16 17 18 14 15 11 10 3 4 5
10:  5 1 2 12 13 20 19 18 14 15 11 10 3 4 8 9 16 17 7 6 5
11:  5 1 20 13 12 2 3 4 8 7 17 16 9 10 11 15 14 18 19 6 5
12:  5 1 20 13 12 2 3 10 11 15 14 18 19 6 7 17 16 9 8 4 5
13:  5 1 20 13 14 15 11 12 2 3 10 9 16 17 18 19 6 7 8 4 5
14:  5 1 20 13 14 15 16 9 10 11 12 2 3 4 8 7 17 18 19 6 5
15:  5 1 20 13 14 15 16 17 18 19 6 7 8 9 10 11 12 2 3 4 5
16:  5 1 20 13 14 18 19 6 7 17 16 15 11 12 2 3 10 9 8 4 5
17:  5 1 20 19 6 7 8 9 10 11 15 16 17 18 14 13 12 2 3 4 5
18:  5 1 20 19 6 7 17 18 14 13 12 2 3 10 11 15 16 9 8 4 5
19:  5 1 20 19 18 14 13 12 2 3 4 8 9 10 11 15 16 17 7 6 5
20:  5 1 20 19 18 17 16 9 10 11 15 14 13 12 2 3 4 8 7 6 5
21:  5 4 3 2 1 20 13 12 11 10 9 8 7 17 16 15 14 18 19 6 5
22:  5 4 3 2 1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5
23:  5 4 3 2 12 11 10 9 8 7 6 19 18 17 16 15 14 13 20 1 5
24:  5 4 3 2 12 13 14 18 17 16 15 11 10 9 8 7 6 19 20 1 5
25:  5 4 3 10 9 8 7 6 19 20 13 14 18 17 16 15 11 12 2 1 5
26:  5 4 3 10 9 8 7 17 16 15 11 12 2 1 20 13 14 18 19 6 5
27:  5 4 3 10 11 12 2 1 20 13 14 15 16 9 8 7 17 18 19 6 5
28:  5 4 3 10 11 15 14 13 12 2 1 20 19 18 17 16 9 8 7 6 5
29:  5 4 3 10 11 15 14 18 17 16 9 8 7 6 19 20 13 12 2 1 5
30:  5 4 3 10 11 15 16 9 8 7 17 18 14 13 12 2 1 20 19 6 5
31:  5 4 8 7 6 19 18 17 16 9 10 3 2 12 11 15 14 13 20 1 5
32:  5 4 8 7 6 19 20 13 12 11 15 14 18 17 16 9 10 3 2 1 5
33:  5 4 8 7 17 16 9 10 3 2 1 20 13 12 11 15 14 18 19 6 5
34:  5 4 8 7 17 18 14 13 12 11 15 16 9 10 3 2 1 20 19 6 5
35:  5 4 8 9 10 3 2 1 20 19 18 14 13 12 11 15 16 17 7 6 5
36:  5 4 8 9 10 3 2 12 11 15 16 17 7 6 19 18 14 13 20 1 5
37:  5 4 8 9 16 15 11 10 3 2 12 13 14 18 17 7 6 19 20 1 5
38:  5 4 8 9 16 15 14 13 12 11 10 3 2 1 20 19 18 17 7 6 5
39:  5 4 8 9 16 15 14 18 17 7 6 19 20 13 12 11 10 3 2 1 5
40:  5 4 8 9 16 17 7 6 19 18 14 15 11 10 3 2 12 13 20 1 5
41:  5 6 7 8 4 3 2 12 13 14 15 11 10 9 16 17 18 19 20 1 5
42:  5 6 7 8 4 3 10 9 16 17 18 19 20 13 14 15 11 12 2 1 5
43:  5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5
44:  5 6 7 8 9 16 17 18 19 20 1 2 12 13 14 15 11 10 3 4 5
45:  5 6 7 17 16 9 8 4 3 10 11 15 14 18 19 20 13 12 2 1 5
46:  5 6 7 17 16 15 11 10 9 8 4 3 2 12 13 14 18 19 20 1 5
47:  5 6 7 17 16 15 11 12 13 14 18 19 20 1 2 3 10 9 8 4 5
48:  5 6 7 17 16 15 14 18 19 20 13 12 11 10 9 8 4 3 2 1 5
49:  5 6 7 17 18 19 20 1 2 3 10 11 12 13 14 15 16 9 8 4 5
50:  5 6 7 17 18 19 20 13 14 15 16 9 8 4 3 10 11 12 2 1 5
51:  5 6 19 18 14 13 20 1 2 12 11 15 16 17 7 8 9 10 3 4 5
52:  5 6 19 18 14 15 11 10 9 16 17 7 8 4 3 2 12 13 20 1 5
53:  5 6 19 18 14 15 11 12 13 20 1 2 3 10 9 16 17 7 8 4 5
54:  5 6 19 18 14 15 16 17 7 8 9 10 11 12 13 20 1 2 3 4 5
55:  5 6 19 18 17 7 8 4 3 2 12 11 10 9 16 15 14 13 20 1 5
56:  5 6 19 18 17 7 8 9 16 15 14 13 20 1 2 12 11 10 3 4 5
57:  5 6 19 20 1 2 3 10 9 16 15 11 12 13 14 18 17 7 8 4 5
58:  5 6 19 20 1 2 12 13 14 18 17 7 8 9 16 15 11 10 3 4 5
59:  5 6 19 20 13 12 11 10 9 16 15 14 18 17 7 8 4 3 2 1 5
60:  5 6 19 20 13 14 18 17 7 8 4 3 10 9 16 15 11 12 2 1 5

1）用map[][]来存储城市之间的连通情况.用used[]存储某个城市的使用情况(即某一个城市是否被访问过).用res[]保存路径

。如res[count] = dep ; 表示的是第count不访问的城市是dep。用cas表示目标城市的序号

/*
* 2181_2.cpp
*
*  Created on: 2013年8月22日
*/

#include <iostream>

using namespace std;

/**
* map[][] :用来保存城市之间的连通情况
* used[] :用来 保存城市的使用情况
* res[] :用来保存路径
* cas :目标城市的标号
*/
const int maxn = 21;
bool map[maxn][maxn];
bool used[maxn];
int res[maxn];
int cas;
int num = 1;

/**
* dep :当前访问城市
* count :当前访问的城市数
*/
void dfs(int dep, int count) {
int i;

//第count个所到达的城市是dep
res[count] = dep;
if (count == 19) { //19步能涉及20个城市
if (map[dep][cas]) {
printf("%d: ", num++);
for (i = 0; i < 20; ++i) {
printf(" %d", res[i]);
}
printf(" %d", cas);
printf("\n");
}

return;
}

for (i = 1; i <= 20; ++i) {
/**
* map[dep][j] :从城市dep到城市j的连通情况
*/
//如果城市dep与城市j连通&&城市j没有使用过
if (map[dep][i] && !used[i]) {
used[i] = true;
dfs(i, count + 1);
used[i] = false;
}
}
}
int main() {
memset(map, 0, sizeof(map));
memset(res, 0, sizeof(res));
memset(used, false, sizeof(used));
int i;
int a, b, c;
for (i = 1; i <= 20; ++i) {
scanf("%d%d%d", &a, &b, &c);
map[i][a] = true;
map[i][b] = true;
map[i][c] = true;
}

while (scanf("%d", &cas) != EOF, cas) {
used[cas] = true;
dfs(cas, 0);
}
}

1. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

2. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

3. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

4. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

5. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

6. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

7. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

8. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

9. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

10. 苏夕其实她的生活挺精彩的，可以和段玥决斗，每天都有不一样的生活，只是苏夕没有机智的头脑，不知道怎么样应付段玥的难题而已

11. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

12. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法