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