2310. [CTSC 2016]科学考察队

【题目描述】

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

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

   为了提高科学考察的效率，牛牛将他带领的考察队分为了 p 个小队，每个小队都能够独立地完成一些工作。他们约定从编号为 S 的集结点出发，最终在

编号为 T 的集结点汇合。在考察的过程中，会遇到重重困难，比如科考队员可以从悬崖的顶端缓缓下降到悬崖底部，却不能从悬崖底部直接攀爬到悬崖顶上，因此输入的路径都是单向的。

   当一个小队沿着一条路径前进后，这个小队将会记录路径上的各种信息与数据。然而有的路径需要考察队自行开辟，开辟一条路径需要耗费一定的材料，将

产生一些费用。由于装备数量有限，牛牛给各小队分配的装备也可能会不同，因此，有些条件困难的路径上，有些小队会因为装备不足而无法通过。但是，牛牛

通过合理地分配装备，确保了每一支小队都能顺利到达编号为 T 的集结点。

   在他们都到达 T 点汇合后，牛牛将会汇总所有的信息与数据，这些信息与数据的总价值即为这次科学考察行动的总收益。其中，如果有多支小队通过了同

一条路径，由于他们记录到的关于这条路径的数据是重复的，因此价值只会计算一次。而开辟路径所花费的费用即为这次科学考察的总支出，同样，即使有多支考察队经过同一条需要开辟的路径，这条路径也只需要开辟一次。

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

【输入格式】

对于每组输入数据：

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

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

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

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

【输出格式】

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

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

【样例输入】

4 4 2 1 4
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

【样例说明】

   地图上有 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个评分参数a1,a2,a3,…,a10。如果选手的输出不合法，则得零分。否则，在你的方案中，若考察总收益为Wuser，你的分数将会由下表给出，若符合表中多个条件，取分数最高的：

【来源】

CTSC2016 D3T3