UOJ Logo Universal Online Judge

UOJ

#203. 【CTSC2016】科学考察队

附件下载 统计

今年正是五四青年节。在这样的大好日子里,青年探险家牛牛带着他的科学考察队去考察一片原始森林。

在考察开始前,牛牛获得了这片原始森林的地图。这片森林里有 $n$ 个集结点,编号为 $1$ 到 $n$ 的整数。在这些集结点之间,存在 $m$ 条路径,编号为 $1$ 到 $m$ 的整数。每条路径以一个集合点为起点,一个集结点为终点。

为了提高科学考察的效率,牛牛将他带领的考察队分为了 $p$ 个小队,每个小队都能够独立地完成一些工作。他们约定从编号为 $S$ 的集结点出发,最终在编号为 $T$ 的集结点汇合。在考察的过程中,会遇到重重困难,比如科考队员可以从悬崖的顶端缓缓下降到悬崖底部,却不能从悬崖底部直接攀爬到悬崖顶上,因此输入的路径都是单向的。

当一个小队沿着一条路径前进后,这个小队将会记录路径上的各种信息和数据。然而有的路径需要考察队自行开辟,开辟一条路径需要耗费一定的材料,将产生一些费用。由于装备数量有限,牛牛给各小队分配的装备也可能会不同,因此,有些条件困难的路径上,有些小队会因为装备不足而无法通过。但是,牛牛通过合理地分配装备,确保了每一支小队都能顺利到达编号为 $T$ 的集结点。

在他们都到达 $T$ 点汇合后,牛牛将会汇总所有的信息与数据,这些信息与数据的总价值即为这次科学考察行动的总收益。其中,如果有多支小队通过了同一条路径,由于他们记录到的关于这条路径的数据是重复的,因此价值只会计算一次。而开辟路径所花费的费用即为这次科学考察的总支出,同样,即使有多支考察队经过同一条需要开辟的路径,这条路径也只需要开辟一次。

现在,牛牛希望为他的 $p$ 个小队设计出合理的行动路径,使得总收益减去总支出的值最大。

输入格式

输入文件 expedition1.in~expedition10.in 已在试题目录下。

对于每组输入数据:

第一行 $5$ 个整数,依次为 $n,m,p,S,T$,意义如题所述。

接下来 $2m$ 行,每两行描述一条路径。

每条路径的第一行三个整数 $u,v,w$,表示这条路径起点为 $u$,终点为 $v$。若 $w>0$,则表示这条路径上的数据价值为 $w$,且不需要开辟。若 $w \leq 0$,则表示这条路径上数据价值为 $0$,且开辟的花费为 $-w$。

每条路径的第二行第一个整数 $k$,表示不能通过这条路径的小队数量。接下来 $k$ 个互不相同的整数,表示这 $k$ 个小队的编号。

输出格式

输入文件 expedition1.out~expedition10.out 已在试题目录下。

对于每组输入数据,你需要依次输出 $p$ 行。第 $i$ 行表示第 $i$ 个小队的行动顺序。

每行第一个数 $k$,表示这个小队总共走过了多少条路径。接下来 $k$ 个数,表示这个小队从 $S$ 前往 $T$ 的过程中依次走过的路径编号。

样例输入

input

4 4 2 1 4
1 3 3
1 2
1 2 5
0
2 3 -2
1 1 
3 4 1
0

output

2 1 4
3 2 3 4

explanation

地图上有 $4$ 个集结点与 $4$ 条路径,其中第 $1$ 支小队能通过的路径有 $1、2、4$,第二支小队能通过的路径有 $2、3、4$。最终 $1$ 小队依次通过 $1、4$ 路径,$2$ 小队依次通过 $2、3、4$ 路径。获取的总收益为 $3+5+1=9$。总支出为 $2$。总收入减总支出的值为 $9-2=7$。

子任务及部分分

每个测试点单独评分。每个测试点你还可能获得部分分。

对于每个测试点,我们设置了 $10$ 个评分参数 $a_1,a_2,a_3,…,a_9,a_{10}$。如果选手的输出不合法,则得零分。否则,在你的方案中,若考察总收益为 $w_{user}$,你的分数将会由下表给出,若符合表中多个条件,取分数最高的:

得分条件得分条件
$10$$w_{usert} \geq a_{10}$$5$$w_{user} \geq a_{5}$
$9$$w_{usert} \geq a_{9}$$4$$w_{user} \geq a_{4}$
$8$$w_{usert} \geq a_{8}$$3$$w_{user} \geq a_{3}$
$7$$w_{usert} \geq a_{7}$$2$$w_{user} \geq a_{2}$
$6$$w_{usert} \geq a_{6}$$1$$w_{user} \geq a_{1}$

所有评分参数文件 expedition1.ans~expedition10.ans 已在试题目录下。 每个评分参数文件共 $10$ 行。其中第 $i$ 行一个非负整数,表示 $a_i$。

如何测试你的输出

在终端中先切换到该试题目录下:(windows用户请用cmd)

cd expedition

我们提供 checker 这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是,在终端中运行

./checker_linux64 <case_no>

其中case_no是测试数据的编号。例如

./checker_linux64 3

将测试 expedition3.out 是否可以接受。(windows用户请使用checker_win32 3)(什么你是windows 64位?放心吧可以运行win32应用程序的。) 当然我们有对应的linux 32位版本:checker_linux32。如果linux用户发现无法运行程序,请尝试执行chmod +x checker_linux64chmod +x checker_linux32后重试。

其它操作系统请安装node.js 然后使用 node checker.js <case_no> 运行checker。

请不要随便更改in文件,防止checker出现不可预知的错误。

下载

选手文件下载

请上传你要提交的文件,并命名为 expedition1.out, expedition2.out, expedition3.out, expedition4.out, expedition5.out, expedition6.out, expedition7.out, expedition8.out, expedition9.out, expedition10.out。如果你提交了 zip 压缩包,我们会为你自动解压。


或者通过如下表单上传: