ICPC Communication Routing Challenge — powered by Huawei中文简化题意

· · 个人记录

有n个点，m条无向边，现有k个消息要从一个叶子节点通过一条路径传输到另一个叶子节点。

边具有容量和长度，平行边间有组数，存在组流限制为100.

有些边有限制，不能从边u到边v。默认为经过同一个节点的边都相连。

通过同一个点的次数最多为200次。

当前一条边所承载的流量总数不得超过边容量。

求最多能同时传送几个消息，输出可以传输的信息总数cnt，以及每个信息最短路径长度的路径。

补充说明：

这cnt个信息将会同时出发，在同样的时间内经过一条边。

样例输入：

8 15 3 1
0 0 0 1 100 1050
1 1 0 1 200 2200
2 1 0 1 200 99400
3 2 0 3 100 450
4 3 0 3 500 1120
5 4 1 2 1000 40000
6 5 2 3 600 10000
7 5 2 3 600 10000
8 6 1 4 120 2500
9 6 1 4 120 450
10 7 1 5 170 1250
11 8 2 5 200 2500
12 9 3 5 100 1250
13 10 3 6 300 1150
14 11 3 7 300 1100
2 5 7
2 6 7
2 6 11
0 4 6 100

样例输出：

1
0 8 0 3 13

输入输出说明：

路径总长度为620 (120+100+100+300=620).

(Note: 0 9 10 12 13也可以是一输出的路径)