POJ 1776 Task Sequences(竞赛图构造哈密顿通路)

链接:http://poj.org/problem?id=1776

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

题意:

　　有一个机器要完成一个作业,给你一个N*N的矩阵,如果M[i][j] = 1,说明完成第i个作业后不用重启机器,机器可以自动继续去完成第j个作业,否则M[i][j]等于0,则说明如果做完第i个作业,想要继续去做第j个作业,那么必须重启机器.对于每两个作业都有M[i][j] = 1或者M[j][i] = 1.让你求出完成这N个作业启动机器的最少次数,以及每次启动完成作业的数量和这些作业的顺序,初始时机器处于关闭状态.

解题思路:

　　把一个机器看成一个点,如果第i个作业完成后不用重启机器,可以继续去做第j个机器,那么就构造有向边<Vi, Vj>.让你找到最少的序列,使得这些序列包含图中所有点一次且仅一次.由于题意的特殊性,构建出来的图是一个竞赛图,竞赛图一定存在一个哈密顿通路,包含图中所有点一次且仅一次,所以最少次数一定是1,且这一次就能完成所有的N项作业.即给出竞赛图,构造哈密顿通路.

注意:

　　由于这题有毒,用scanf(),一个数字一个数字的读会超时,所以借用了某大神的输入技巧.

代码:

 #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-'';}

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

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

                 if(j > i && u == )

                     map[j][i] = ;

             }

         }

         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 ;

 }