解题思路

本题要求将竞赛图划分为最少的路径覆盖，每个路径对应一个任务序列，机器的启动次数等于路径覆盖数。竞赛图的特性和相关定理是解决此题的关键。

问题分析

1. 竞赛图定义：任意两个节点 (i) 和 (j) 之间至少存在一条有向边（(i \to j) 或 (j \to i)）。
2. 路径覆盖目标：将图中所有节点划分为若干不相交的路径，使得路径数量最少。
3. 关键性质：
   • 竞赛图的强连通分量（SCC）缩点后形成一个全序的有向无环图（DAG），即任意两个缩点之间有且仅有一条有向边。
   • 根据Dilworth定理，竞赛图的最少路径覆盖数等于其强连通分量的个数。

算法步骤

1. 强连通分量分解：使用Tarjan算法找出图中的所有强连通分量。每个强连通分量对应一个独立的路径覆盖单元。
2. 构造哈密顿路径：对每个强连通分量，利用贪心算法构造一条哈密顿路径，确保路径中相邻节点间存在有向边。

解决代码

#define _CRT_SECURE_NO_DEPRECATE
 
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 1000000000
#define eps 0.0001
using namespace std;
 
int n;
int g[1005][1005];
int nex[1005];
char s[2005];
 
void solve()
{
	int head = 1;
	int t;
	for (int i = 2; i <= n; i++)//遍历未加入哈密顿的点
	{
		bool flag = 0;
		for (int j = head; j != -1; j = nex[j])//遍历已经是哈密顿的点
		{
			if (g[i][j])
			{
				if (j == head)
					head = i;
				else
					nex[t] = i;
 
				nex[i] = j;
				flag = 1;
				break;
			}
			else
				t = j;
		}
 
		if (flag == 0)
			nex[t] = i;
	}
 
	printf("1\n%d\n", n);
	printf("%d", head);
	for (head = nex[head]; head != -1; head = nex[head])
		printf(" %d", head);
	printf("\n");
}
 
int main() 
{
	while (~scanf("%d", &n))
	{
		memset(nex, -1, sizeof(nex));
 
		for (int i = 1; i <= n; i++)
		{
			getchar();
			scanf("%[^\n]", s);
			int t = 1;
			for (int j = 0; t <= n; j = j + 2, t++)
				g[i][t] = s[j] - '0';
		}
 
		solve();
	}
	return 0;
}