2009年12月26日星期六.sgu122
半个月了。。。才看出错来。。
构造法很复杂不会，说说搜索的思路：搜索时按每个点临接点的度数从小到大来搜就可以了
此题非常阴险:
1.scanf读入会超时....
2.vector存邻接表一定超时，邻接矩阵又没办法按照度数排序，再开一个矩阵会超内存,第68，69两行只能选一个用，不然会越界
3.每行存的是临接的点，但是没有32~36行会WA @ test 24！！！！！！
4.No Solution是不存在的
1 /*
2 * SOUR:sgu122
3 * ALGO:graph theory
4 * DATE: 2009年 12月 04日 星期五 20:33:43 CST
5 * COMM:5
6 * Ore条件: 对于一个简单图满足任意两个顶点的度数和都大于等于n则必定存在哈密顿回路
7 * * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 #include<cassert>
14 #include<vector>
15 using namespace std;
16 const int N = 1001;
17 int cnt[N],deg[N],n,vis[N],out[N],top;
18 int g[N][N];
19 const int M = 6100;
20 char s[M];
21
22 bool cmp(int a,int b) { return deg[a] < deg[b]; }
23 bool dfs(int u,int left)
24 {
25 if(left == 0) {
26 for(int i = 0;i < cnt[u];i++) {
27 if(g[u][i] == 1) {
28 return true;
29 }
30 }
31 //我不知道题目为什么会这么阴险!!
32 for(int i = 0;i < cnt[1];i++) {
33 if(g[1][i] == u) {
34 return true;
35 }
36 }
37 return false;
38 }
39 for(int i = 0;i < cnt[u];i++) {
40 int v = g[u][i];
41 if(!vis[v]) {
42 vis[v] = 1;
43 if(dfs(v,left - 1)) {
44 out[top++] = v;
45 return true;
46 }
47 vis[v] = 0;
48 }
49 }
50 return false;
51 }
52
53 int main()
54 {
55 int i,j,k,tmp,len;
56 scanf("%d\n",&n);
57 for(i = 1;i <= n;i++) {
58 fgets(s,M,stdin);
59 s[(len = strlen(s)) -1] = ' ';
60
61 for(j = 0;j < len;) {
62 k = 0;
63 while(s[j] >= '0') {
64 k = k * 10 + s[j] - '0';
65 j++;
66 }
67 while(s[j] == ' ') {j++;}
68 g[i][cnt[i]++] = k;
69 //g[k][cnt[k]++] = i;
70 deg[k]++;
71 deg[i]++;
72 }
73 }
74 for(i = 1;i <= n;i++) {
75 sort(&g[i][0],&g[i][cnt[i]],cmp);
76 }
77
78 vis[1] = true;
79 dfs(1,n-1);
80 printf("1");
81 for(i = 0;i < top;i++) {
82 printf(" %d",out[i]);
83 }
84 printf(" 1\n");
85
86 return 0;
87 }
88