Task Sequences
| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 2062 |
|
Accepted: 583 |
|
Special Judge |
Description
Tom has received a lot of tasks from his boss, which are boring to deal with by hand. Fortunately,Tom got a special machine - Advanced Computing Machine (ACM) to help him.
ACM works in a really special way. The machine can finish one task in a short time, after it‘s finishing one task, it should smoothly move to the next one, otherwise the machine will stop automatically. You must start it up again to make it continue working.
Of course, the machine cannot move arbitrarily from one task to another. So each time before it starts up, one task sequence should be well scheduled. Specially, a single task also can be regarded as a sequence. In the sequence, the machine should be able
to smoothly move from one task to its successor (if exists). After started up, the machine always works according to the task sequence, and stops automatically when it finishes the last one. If not all the tasks have been finished, the machine has to start
up again and works according to a new sequence. Of course, the finished tasks can‘t be scheduled again.
For some unknown reasons, it was guaranteed that for any two tasks i and j, the machine can smoothly move from i to j or from j to i or both. Because the startup process is quite slow, Tom would like to schedule the task sequences properly, so that all the
tasks can be completed with minimal number of startup times. It is your task to help him achieve this goal.
Input
Input contains several testcases. For each testcase, the first line contains only one integer n, (0 < n <= 1,000), representing the number of tasks Tom has received. Then n lines follow. Each line contains n integers, 0 or 1, separated
by white spaces. If the jth integer in the ith line is 1, then the machine can smoothly move from task i to task j, otherwise the machine can not smoothly move from task i to task j. The tasks are numbered from 1 to n.
Input is terminated by end of file.
Output
For each testcase, the first line of output is only one integer k, the minimal number of startup times needed. And 2k lines follow, to describe the k task sequences. For each task sequence, the first line should contain one integer
m, representing the number of tasks in the sequence. And the second line should contain m integers, representing the order of the m tasks in the sequence. Two consecutive integers in the same line should be separated by just one white space. Extra spaces are
not allowed. There may be several solutions, any appropriate one is accepted.
Sample Input
3
0 1 1
1 0 1
0 0 0
Sample Output
1
3
2 1 3
Source
竞赛图:图中的任意两点间有且仅有一条有向弧连接
求竞赛图中的哈密顿路的算法：
首先,由数学归纳法可证竞赛图在n>=2时必存在哈密顿路；
(1)n=2时显然；
(2)假设n=k时,结论成立,哈密顿路为V1,V2,...,Vi,...,Vk；
现添加第k+1个结点，若存在弧<Vi,Vk+1>和弧<Vk+1,Vi+1>，则可得哈密顿回路V1,V2,...,Vi,Vk+1,Vi+1,...,Vk；
若不存在上述的vi,考虑到Vk+1与v1~vk的连通状况,则只有下面种原哈密顿路的情况：
1.所有的Vi(1<i<k)与Vk+1的弧的方向都是<Vi,Vk+1>，那么可得哈密顿回路V1,V2,...,Vi,...,Vk,Vk+1；
2.所有的Vi(1<i<k)与Vk+1的弧的方向都是<Vk+1,Vi>，那么可得哈密顿回路Vk+1,V1,V2,...,Vi,...,Vk；
3.存在一个中间结点m，使得所有的Vi(1<=i<=m)与Vk+1的弧方向为<Vk+1,Vi>,所有的Vj(m<j<=k)与Vk+1的弧的方向为<Vj,Vk+1>，这时依然可以构造哈密顿路 V1,V2,...,Vi,...,Vk,Vk+1；
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/3/25 20:14:43
File Name :12.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=1010;
int next[maxn],pic[maxn][maxn];
int n;
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
while(cin>>n){
memset(pic,0,sizeof(pic));
string str;
getline(cin,str);
for(int i=1;i<=n;i++){
getline(cin,str);
for(int j=1;j<=n;j++)
pic[i][j]=str[(j-1)*2]-‘0‘;
}
memset(next,0,sizeof(next));
int head=1,t;
for(int k=2;k<=n;k++){
bool flag=0;
for(int i=head;i;i=next[i])
if(pic[k][i]){
if(i==head)head=k;
else next[t]=k;
next[k]=i;
flag=1;break;
}
else t=i;
if(!flag)next[t]=k;
}
cout<<1<<endl<<n<<endl;
for(int i=head;i;i=next[i]){
if(i!=head)cout<<" ";
cout<<i;
}
cout<<endl;
}
return 0;
}
POJ 1776 竞赛图的哈密尔顿回路,布布扣,bubuko.com
POJ 1776 竞赛图的哈密尔顿回路
原文：http://blog.csdn.net/xianxingwuguan1/article/details/22094317
