#2992. 「CTSC 2016」科学考察队

题目类型:答案提交 评测方式:Special Judge
上传者: YMDragon

题目描述

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

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

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

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

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

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

输入格式

输入文件 expedition1.in~expedition10.in 已在附加文件中。

对于每组输入数据:

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

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

每条路径的第一行三个整数 u,v,wu,v,w,表示这条路径起点为 uu,终点为 vv。若 w>0w > 0,则表示这条路径上的数据价值为 ww,且不需要开辟。若 w0w \ge 0,则表示这条路径上数据价值为 00,且开辟的花费为 w−w

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

输出格式

输出文件为 expedition1.out~expedition10.out,分别对应相应的输入文件。

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

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

样例

样例输入

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

样例输出

2 1 4
3 2 3 4

样例说明

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

数据范围与提示

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

对于每个测试点,我们设置了 1010 个评分参数 a1,a2,a3,,a9,a10a_1, a_2, a_3, \ldots , a_9, a_{10}。如果选手的输出不合法,则得零分。否则,在你的方案中,若考察总收益为 wuw_u,你的分数将为:若 wuaiw_u\ge a_i,则获得 ii 分,若多个 ii 符合条件,取 ii 最大的。