P5421 [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~

输入文件 expedition1.out~expedition10.out 已在试题目录下。 对于每组输入数据，你需要依次输出 $p$ 行。第 $i$ 行表示第 $i$ 个小队的行动顺序。 每行第一个数 $k$，表示这个小队总共走过了多少条路径。接下来 $k$ 个数，表示这个小队从 $S$ 前往 $T$ 的过程中依次走过的路径编号。

### 样例一解释 地图上有 $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}$，且存在一个最大的 $i$, 使得 $w_{user}~\geq~a_{i}$，则你获得 $i$ 分。 所有评分参数文件 expedition1.ans~expedition10.ans 已在试题目录下。 每个评分参数文件共 $10$ 行。其中第 $i$ 行一个非负整数，表示 $a_i$。 ### 输入数据下载 [下载链接](https://share.weiyun.com/52vCCzr)