HDU3414 Tour Route(竞赛图寻找哈密顿回路)

链接:http://acm.hdu.edu.cn/showproblem.php?pid=3414

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

题意:

　　某个城市有N个景点,某一天来了一批游客想参观这些景点,他们的要求是这些景点都要去且每个景点仅去一次.特殊的是,对于任意两个景点,路都是单向的.即要么能从Ａ景点到Ｂ景点,要么可以从B景点到A景点,不存在双向或者不连通的情况.让你找到一个回路,从某个景点出发,经过全部景点一次且仅一次,最后又能回到起点.

思路:

　　很显然是让在竞赛图中寻找哈密顿回路,但是由于竞赛图一定存在哈密顿路径,但不一定存在哈密顿回路,所以需要枚举所有起点,构造一个哈密顿路径,然后判断起点和终点是否连通就可以了.

代码:

 #include <iostream>

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <vector>

 using namespace std;

 typedef long long LL;

 const int maxN = ;

 inline void read(int &a){char c;while(!(((c=getchar())>='')&&(c<='')));a=c-'';while(((c=getchar())>='')&&(c<=''))(a*=)+=c-'';}

 void Hamilton(int ans[maxN + ], int map[maxN + ][maxN + ], int n, int st) {

     int nxt[maxN + ];

     memset(nxt, -, sizeof(nxt));

     int head = st;

     for(int i = ; i <= n; i++) {

         if(i == st)continue;

         if(map[i][head]) {

             nxt[i] = head;

             head = i;

         }else {

             int pre = head, pos = nxt[head];

             while(pos != - && !map[i][pos]) {

                 pre = pos;

                 pos = nxt[pre];

             }

             nxt[pre] = i;

             nxt[i] = pos;

         }

     }

     int cnt = ;

     for(int i = head; i != -; i = nxt[i]) ans[++cnt] = i;

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int N;

     while(~scanf("%d", &N) && N) {

         int map[maxN + ][maxN + ] = {};

         for(int i = ; i <= N; i++) {

             for(int j = ; j <= N; j++) {

                 int u; read(u);

                 map[i][j] = u;

             }

         }

         if(N == ){ printf("1\n");continue; }

         int ans[maxN + ] = {}, i;

         for(i = ; i<= N; i++) {

             Hamilton(ans, map, N, i);

             if(map[ans[N]][ans[]]) {

                 for(int j = ; j <= N; j++) {

                     printf(j ==  ? "%d":" %d", ans[j]);

                 }

                 break;

             }

         }

         if(i > N)printf("-1");

         printf("\n");

     }

     return ;

 }