2010-02-04.ural1063-pku1756
ALGO:graph theory and IDFS
题目中给给出了m(1 ≤ m ≤ 100)条无向边，点是1-6，意思就是在这6个点上添加一些边组成欧拉回路，
并且要求点的和最小
欧拉路存在的条件:奇度数顶点的个数为0或2且图是连通的。
我一开始的想法是：
最多只有6个点，完全图的边的数量不过5+4+3+2+1=15条，我就想枚举这些边的组合。
一共 2^15 种可能才 32 × 1024种可能。看了样例才发现可以添加重边。。。
然后就只能搜了，怎么搜呢，迭代加深搜最好，但是要注意，有可能多添一条边，但是花费却变少了。
然后就是最坏的情况也只能添加5条边
6
1 1
2 2
3 3
4 4
5 5
6 6
然后就是写代码了，题目还是比较不好写正确的
1756 Domino Puzzle 42
pku只有42人过了。。
1
2 const int N = 8;
3 const int M = 512;
4 int edge[M][2],m,top;
5 int vis[N],g[N][N],deg[N];
6 int st[N],n; //the node exists in graph
7 int exist[N],res;
8 int save[M][2],sp;
9 //http://www.cppblog.com/schindlerlee/
10 void dfs2(int u)
11 {
12 vis[u] = 1;
13 for (int i = 1;i <= 6;i++) {
14 if (g[u][i] && !vis[i]) {
15 dfs2(i);
16 }
17 }
18 }
19
20 bool connected()
21 {
22 memset(vis,0,sizeof(vis));
23 dfs2(st[0]);
24 for (int i = 0;i < n;i++) {
25 if (!vis[st[i]]) {
26 return false;
27 }
28 }
29 return true;
30 }
31
32 int goaldepth;
33 bool dfs(int depth,int curres,int begi,int begj)
34 //加上begi和begj能从980ms -> 16ms
35 {
36 int i,j;
37 if (depth == goaldepth) {
38 int cnt = 0;
39 for (i = 1;i <= 6;i++) {
40 if (deg[i] & 1) {
41 cnt++;
42 }
43 }
44 if (curres < res && (cnt == 0 || cnt == 2) && connected()) {
45 res = curres;
46 sp = top - m;
47 for (i = 0;i < sp;i++) {
48 save[i][0] = edge[i+m][0];
49 save[i][1] = edge[i+m][1];
50 }
51 return true;
52 }
53 return false;
54 }
55 for (i = begi;i < n;i++) {
56 for (j = begj;j < n;j++) {
57 if (i != j) {
58 int a = st[i],b = st[j];
59 if (curres + a + b >= res) { continue; }
60 g[a][b]++;
61 g[b][a]++;
62 deg[a]++;
63 deg[b]++;
64 edge[top][0]=a, edge[top][1]=b,top++;
65 dfs(depth+1,curres + a + b,i,j);
66 top--;
67 g[a][b]--;
68 g[b][a]--;
69 deg[a]--;
70 deg[b]--;
71 }
72 }
73 }
74 }
75
76 int main()
77 {
78 int i,j,k;
79 scanf("%d",&m);
80 for (i = 0;i < m;i++) {
81 int a,b;
82 scanf("%d%d",&a,&b);
83 edge[i][0] = a;
84 edge[i][1] = b;
85 exist[a] = 1;
86 exist[b] = 1;
87 g[a][b] ++;
88 g[b][a] ++;
89 deg[a]++;
90 deg[b]++;
91 }
92 for (i = 1;i <= 6;i++) {
93 if (exist[i]) {
94 st[n++] = i;
95 }
96 }
97
98 res = maxint;
99 for (i = 0;i <= 5;i++) {
100 top = m;
101 goaldepth = i;
102 dfs(0,0,0,0);
103 }
104
105 printf("%d\n",res);
106 printf("%d\n",sp);
107 for (i = 0;i < sp;i++) {
108 printf("%d %d\n",save[i][0],save[i][1]);
109 }
110
111 return 0;
112 }
113