Why so serious? --[NKU]schindlerlee

2010-02-04.ural1063-pku1756 graph theory and IDFS 此题在pku上42人AC

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 


posted on 2010-02-04 14:42 schindlerlee 阅读(1094) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理