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(),一个数字一个数字的读会超时,所以借用了某大神的输入技巧.

代码:

 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 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';}
15 
16 inline void Insert(int arv[], int &len, int index, int key){ 
17     if(index > len) index = len;
18     len++;
19     for(int i = len - 1; i >= 0; --i){
20         if(i != index && i)arv[i] = arv[i - 1];
21         else{arv[i] = key; return;}
22     }
23 }
24 
25 void Hamilton(int ans[maxN + 7], int map[maxN + 7][maxN + 7], int n){
26     int ansi = 1;
27     ans[ansi++] = 1;
28     for(int i = 2; i <= n; i++){
29         if(map[i][ans[ansi - 1]] == 1)
30             ans[ansi++] = i;
31         else{
32             int flag = 0;
33             for(int j = ansi - 2; j > 0; --j){
34                 if(map[i][ans[j]] == 1){
35                     flag = 1;
36                     Insert(ans, ansi, j + 1, i);
37                     break;
38                 }
39             }
40             if(!flag)Insert(ans, ansi, 1, i);
41         }
42     }
43 }
44 
45 int main()
46 {
47     //freopen("input.txt", "r", stdin);
48     int N;
49     while(~scanf("%d", &N)){
50         int map[maxN + 7][maxN + 7] = {0};
51         for(int i = 1; i <= N; i++){
52             for(int j = 1; j <= N; j++){
53                 int u;
54                 read(u);
55                 if(j > i && u == 1)
56                     map[j][i] = 1;
57             }
58         }
59         printf("%d
%d
", 1, N);
60         int ans[maxN + 7] = {0};
61         Hamilton(ans, map, N);
62         for(int i = 1; i <= N; i++)
63             printf(i == 1 ? "%d":" %d", ans[i]);
64         printf("
");
65     }
66     return 0;
67 }