POJ 2438 Children's Dining(哈密顿回路)

题目链接:http://poj.org/problem?id=2438

本文链接:http://www.cnblogs.com/Ash-ly/p/5452615.html

题意:

　　有2*N个小朋友要坐在一张圆桌上吃饭,但是每两个小朋友之间存在一种关系,即敌人或者朋友,然后需要让你安排一个座位次序,使得相邻的两个小朋友都不会是敌人.假设每个人最多有N-1个敌人.如果没有输出"No solution!".

思路:

　　如果按照题意直接建图,每个点表示一个小朋友,小朋友之间的敌对关系表示两个点之间有边.问题是求小朋友围着桌子的座次就是求图中的一个环,但是要求这个环不能包含所给出的每条边,所有没给出的边却是可以用的,也就是说本题实际上是在上面建的图的反图上求解一个环,使得该环包含所有点.包含所有点的环一定是一条哈密顿回路,所以题目就是求所给图的反图上的一条哈密顿回路.

　　题目中给了一个特殊条件,就是一共有2*N个小朋友,但是每个人最多有N-1个敌人,也就是说,每个小朋友可以选择坐在身边的小朋友数大于n + 1,这就意味着在建立的反图中,每个点的度数大于N+1,由Dirac定理可知,此图一定存在哈密顿回路,所以答案不会出现"No solution!",即直接构造哈密顿回路就可以了.

代码:

  1 #include <iostream>
  2 #include <cmath>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <queue>
  8 #include <stack>
  9 #include <vector>
 10 
 11 using namespace std;
 12 typedef long long LL;
 13 const int maxN = 400;
 14 
 15 inline void reverse(int arv[maxN + 7], int s, int t){
 16     int temp;
 17     while(s  < t){
 18         temp = arv[s];
 19         arv[s] = arv[t];
 20         arv[t] = temp;
 21         s++;
 22         t--;
 23     }
 24 }
 25 
 26 void Hamilton(int ans[maxN + 7], bool map[maxN + 7][maxN + 7], int n){
 27     int s = 1, t;
 28     int ansi = 2;
 29     int i, j;
 30     int w;
 31     int temp;
 32     bool visit[maxN + 7] = {false};
 33     for(i = 1; i <= n; i++) if(map[s][i]) break;
 34     t = i;
 35     visit[s] = visit[t] = true;
 36     ans[0] = s;
 37     ans[1] = t;
 38     while(true){
 39         while(true){
 40             for(i = 1; i <= n; i++){
 41                 if(map[t][i] && !visit[i]){
 42                     ans[ansi++] = i;
 43                     visit[i] = true;
 44                     t = i;
 45                     break;
 46                 }
 47             }
 48             if(i > n) break;
 49         }
 50         w = ansi - 1;
 51         i = 0;
 52         reverse(ans, i, w);
 53         temp = s;
 54         s = t;
 55         t = temp;
 56         while(true){
 57             for(i = 1; i <= n; i++){
 58                 if(map[t][i] && !visit[i]){
 59                     ans[ansi++] = i;
 60                     visit[i] = true;
 61                     t = i;
 62                     break;
 63                 }
 64             }
 65             if(i > n) break;    
 66         }
 67         if(!map[s][t]){
 68             for(i = 1; i < ansi - 2; i++)
 69                 if(map[ans[i]][t] && map[s][ans[i + 1]])break;
 70             w = ansi - 1;
 71             i++;
 72             t = ans[i];
 73             reverse(ans, i, w);
 74         }
 75         if(ansi == n) return;
 76         for(j = 1; j <= n; j++){
 77             if(visit[j]) continue;
 78             for(i = 1; i < ansi - 2; i++)if(map[ans[i]][j])break;
 79                 if(map[ans[i]][j]) break;
 80         }
 81         s = ans[i - 1];
 82         t = j;
 83         reverse(ans, 0, i - 1);
 84         reverse(ans, i, ansi - 1);
 85         ans[ansi++] = j;
 86         visit[j] = true;
 87     }
 88 }
 89 
 90 int main(){
 91     //freopen("input.txt", "r", stdin);
 92     int N, M;
 93     while(~scanf("%d%d", &N, &M) && (N || M)){
 94         N *= 2;
 95         bool map[maxN + 7][maxN + 7] = {0};
 96         int ans[maxN + 7] = {0};
 97         int ansi = 0;
 98         for(int i = 0; i <= N; i++)
 99             for(int j = 0; j <= N; j++)
100                 i == j ? map[i][j] = map[j][i] = 0 : map[i][j] = map[j][i] = 1;
101         memset(ans, 0, sizeof(ans));
102         for(int i = 1; i <= M; i++){
103             int u, v;
104             scanf("%d%d", &u, &v);
105             map[u][v] = map[v][u]= 0;
106         }
107         Hamilton(ans, map, N);
108         for(int i = 0; i < N; i++)
109             printf(i == 0 ? "%d":" %d", ans[i]);
110         printf("
");
111 
112     }
113     return 0;
114 }