链接:http://acm.hdu.edu.cn/showproblem.php?pid=3414
本文链接:http://www.cnblogs.com/Ash-ly/p/5459540.html
题意:
某个城市有N个景点,某一天来了一批游客想参观这些景点,他们的要求是这些景点都要去且每个景点仅去一次.特殊的是,对于任意两个景点,路都是单向的.即要么能从Ａ景点到Ｂ景点,要么可以从B景点到A景点,不存在双向或者不连通的情况.让你找到一个回路,从某个景点出发,经过全部景点一次且仅一次,最后又能回到起点.
思路:
很显然是让在竞赛图中寻找哈密顿回路,但是由于竞赛图一定存在哈密顿路径,但不一定存在哈密顿回路,所以需要枚举所有起点,构造一个哈密顿路径,然后判断起点和终点是否连通就可以了.
代码:
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 = 1000; 14 15 inline void read(int &a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} 16 17 void Hamilton(int ans[maxN + 7], int map[maxN + 7][maxN + 7], int n, int st) { 18 int nxt[maxN + 7]; 19 memset(nxt, -1, sizeof(nxt)); 20 int head = st; 21 for(int i = 1; i <= n; i++) { 22 if(i == st)continue; 23 if(map[i][head]) { 24 nxt[i] = head; 25 head = i; 26 }else { 27 int pre = head, pos = nxt[head]; 28 while(pos != -1 && !map[i][pos]) { 29 pre = pos; 30 pos = nxt[pre]; 31 } 32 nxt[pre] = i; 33 nxt[i] = pos; 34 } 35 } 36 int cnt = 0; 37 for(int i = head; i != -1; i = nxt[i]) ans[++cnt] = i; 38 } 39 40 int main() 41 { 42 //freopen("input.txt", "r", stdin); 43 int N; 44 while(~scanf("%d", &N) && N) { 45 int map[maxN + 7][maxN + 7] = {0}; 46 for(int i = 1; i <= N; i++) { 47 for(int j = 1; j <= N; j++) { 48 int u; read(u); 49 map[i][j] = u; 50 } 51 } 52 if(N == 1){ printf("1 ");continue; } 53 int ans[maxN + 7] = {0}, i; 54 for(i = 1; i<= N; i++) { 55 Hamilton(ans, map, N, i); 56 if(map[ans[N]][ans[1]]) { 57 for(int j = 1; j <= N; j++) { 58 printf(j == 1 ? "%d":" %d", ans[j]); 59 } 60 break; 61 } 62 } 63 if(i > N)printf("-1"); 64 printf(" "); 65 } 66 return 0; 67 }