ZOJ 3332 Strange Country II (竞赛图构造哈密顿通路)

链接:http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=3332

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

题意:

　　给你一个N,代表含有N个点的竞赛图,接着的N * (N- 1) / 2行两个点u, v,代表存在有向边<u,v>,问是否能构造出来一个哈密顿通路.

思路:

　　竞赛图一定含有哈密顿通路,不一定含有哈密顿回路.则不可能出现不存在的情况,直接构造就可以,至于方法可看我的另外一篇文章:http://www.cnblogs.com/Ash-ly/p/5452580.html.

注意:

　　构造的时候从后往前寻找1或者0的时候一定是按照当前序列的顺序查找到,而不是按照点本身的顺序查找,在这里WA了几次.

代码:

 #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 = ;

 //The arv[] length is len, insert key befor arv[index]

 inline void Insert(int arv[], int &len, int index, int key){

     if(index > len) index = len;

     len++;

     for(int i = len - ; i >= ; --i){

         if(i != index && i)arv[i] = arv[i - ];

         else{arv[i] = key; return;}

     }

 }

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

     int ansi = ;

     ans[ansi++] = ;

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

         if(map[i][ans[ansi - ]] == )

             ans[ansi++] = i;

         else{

             int flag = ;

             for(int j = ansi - ; j > ; --j){//在当前序列中查找0/1

                 if(map[i][ans[j]] == ){

                     flag = ;

                     Insert(ans, ansi, j + , i);

                     break;

                 }

             }

             if(!flag)Insert(ans, ansi, , i);

         }

     }

 }

 int main()

 {

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

     int t;

     scanf("%d", &t);

     while(t--){

         int N;

         scanf("%d", &N);

         int M = N * (N - ) / ;

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

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

             int u, v;

             scanf("%d%d", &u, &v);

             if(u < v)map[v][u] = ;//建图,map[v][u] = 1,代表存在边<u, v>,且 u < v.

         }

         int ans[maxN + ] = {};

         Hamilton(ans, map, N);

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

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

         printf("\n");

     }

     return ;

 }

代码2:

 #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 nxt[maxN + ];//用数组模拟链表

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

     int head = ;

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

         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)){

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

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

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

                 int u;

                 read(u);

                 map[i][j] = u;

             }

         }

         printf("%d\n%d\n", , N);

         int ans[maxN + ] = {};

         Hamilton(ans, map, N);

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

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

         printf("\n");

     }

     return ;

 }

巴特西

ZOJ 3332 Strange Country II (竞赛图构造哈密顿通路)

最新文章

热门文章