UOJ Logo Universal Online Judge

UOJ

#554. 【UNR #4】挑战哈密顿

附件下载 统计

这是一道提交答案题。比赛时提交此题显示的成绩就是最终成绩。

在线性解决三染色后,出题人 03 着手于研究图上哈密顿链问题:给你一个 $n$ 个点,$m$ 条边的有向图,请你找到一条经过每个结点恰好一次的路径。

03 生成了一大堆图,在确定这些图都存在至少一条哈密顿链之后,03 便扔给了选手。

看到选手面露难色,03 摆了摆手:“不要那么为难自己。如果找不到哈密顿链,那么告诉我一条尽量长的不重复经过结点的路径就好了。”

选手立刻拍了桌子:“即使是求最长路,也是 NP 完全问题啊!出题人怎么能随便找个 NP 完全问题随便找几个图,就把题出出来了呢?”

但 03 背过身去指了指考场上高高挂起的横幅 “沉着冷静,认真答题” 就走了。

选手冷静下来之后果然发现数据有蹊跷。虽然测试点各有特点,但存在一个统一的简洁算法能够通过所有测试点。那么聪明的你也能发现这个算法吗?

输入格式

这是一道提交答案题,共有 $10$ 组输入数据,这些数据命名为 hamil1.in ~ hamil10.in

第一行两个正整数 $n, m$。

第二行 $10$ 个数字,第 $i$ 个数字表示 $a_i$,表示评分参数。

接下来 $m$ 行,每行 $2$ 个正整数 $u, v$,表示有一条从 $u$ 到 $v$ 的有向边。

输出格式

对于每组输入数据,你需要提交相应的输出文件 hamil1.out ~ hamil10.out

每组数据第一行一个正整数 $k$,表示路径上节点个数。

第二行 $k$ 个正整数,表示路径依次经过的点的序列。

样例一

input

3 3
3 3 3 3 3 3 3 3 3 3
1 2
1 3
2 3

output

3
1 2 3

explanation

注意边是有向的。

选手的提交在该测试点上可以获得 10 分。

样例二

input

4 4
1 1 2 2 3 3 4 4 4 4
1 2
2 1
1 3
4 2

output

2
2 1

explanation

选手的提交在该测试点上可以获得 4 分。

注意你不需要提交最优解。

评分标准

对于每个测试点:

  • 若你的输出不合法,你的得分为0。否则设你的方案中节点个数个数为$k$。
  • 你的得分为 $\sum \limits_{i=1}^{10} [k \ge a_i]$,即你的 $k$ 大于等于多少个 $a_i$ ,就得几分。

数据范围

对于所有数据,满足$1 \le n,m \le 500000$。

保证无重边、自环,且存在至少一条哈密顿路径。

下载

输入数据及checker下载

请上传你要提交的文件,并命名为 hamil1.out, hamil2.out, hamil3.out, hamil4.out, hamil5.out, hamil6.out, hamil7.out, hamil8.out, hamil9.out, hamil10.out。如果你提交了 zip 压缩包,我们会为你自动解压。


或者通过如下表单上传: