CF1576A.Communication Routing Challenge

In optical communication networks, appropriate path planning can improve the utilization of communication resources and bring a smooth communication experience to users. The following figure shows an inter-satellite optical communication network. User messages are sent from one terrestrial base station (nodes $4$ to $7$) and transmitted through satellites (nodes $0$ to $3$) in space to another terrestrial base station (nodes $4$ to $7$).

In the preceding figures, there are communication connections (edges for short) between base stations and satellites and between satellites. The base stations and satellites are referred to as nodes.

User messages are transmitted on these edges and referred to as flows. Some users may make video calls with friends, and some users may send short messages to their family members. Therefore, the message traffic (called flow rate) of each user differs.

There are many parallel edges (for example, edges $0$, $1$, and $2$) between two nodes, and the capacity of each edge also differs. Larger capacity indicates that more user messages can be transmitted, as well as shorter transmission distance indicates lower latency and better communication quality.

Nodes also have their internal structure. As shown below, some edges inside a node cannot communicate with each other because these edges (constrained edge pair) are not fully connected. For example, edge $5$ and edge $7$ inside node $2$ cannot communicate with each other, and therefore flows cannot pass through node $2$ by traversing the two unconnected edges.

Now, in the input network, the source node, target node, and required flow rate for each user flow are specified. Because network resources are limited, paths may not be successfully calculated for all user flows. We hope that you can provide a solution with the highest score.

Note, that

• all edges are undirected, so flows may come in both directions,
• edges has both capacity and length (named distance),
• several flows may use the same edge,
• flows may come through the same edge in opposite directions simultaneously,
• for the purpose of this problem, there is no difference between satellites and base stations, so flows may come through several base stations before reaching the destination station.

Constraints

1. The capacity of each edge is limited. The total rate of all flows carried by an edge cannot exceed the capacity of the edge. The capacity limits the total flows in both directions.
2. The calculated flow path does not allow loops or cycles.
3. Due to the hardware limitation inside satellites, the number of flows passing through a node (including source and target node) cannot exceed the site flow limit ($\mathit{SFL}$) of the node. The value of $\mathit{SFL}$ is $200$.
4. There are multiple parallel edges between two nodes, which may belong to different groups. Links in each group are managed by the same chip on a node, and there is a group flow limit ($\mathit{GFL}$). The total number of different flows on all the edges in a group cannot exceed the $\mathit{GFL}$ of the group. The value of $\mathit{GFL}$ is $100$.
5. By default, all edges are connected to each other in each node. But there are some constrained edge pairs — the pairs of edges inside specified nodes that cannot communicate with each other.
6. You can make no more than $2$ submissions on each $5$ minutes interval.

在光通信网络中，合理的路径规划可以提高通信资源的利用率，并为用户提供流畅的通信体验。下图展示了一个星间光通信网络：用户消息从一个地面基站（节点 $4$ 至 $7$）发出，经由空间中的卫星（节点 $0$ 至 $3$）中转，最终抵达另一个地面基站（节点 $4$ 至 $7$）。

在上述图中，地面基站与卫星之间、以及卫星与卫星之间存在通信连接（简称为边）。地面基站和卫星统称为节点。

用户消息在这些边上进行传输，称为流（flow）。部分用户可能与朋友进行视频通话，另一些用户则可能向家人发送短消息，因此每位用户的业务流量（称为流速率，flow rate）各不相同。

两个节点之间可能存在多条平行边（例如边 $0$、$1$ 和 $2$），且每条边的容量也各不相同。容量越大，表示可承载的用户消息越多；同时，传输距离越短，意味着时延越低，通信质量越好。

节点内部也具有特定结构。如下图所示，由于某些边（称为受限边对，constrained edge pair）在节点内部未完全连通，导致它们彼此之间无法通信。例如，在节点 $2$ 内部，边 $5$ 与边 $7$ 无法相互通信，因此流无法通过节点 $2$ 同时经过这两条互不连通的边。

现在，在输入网络中，每个用户流的源节点、目标节点及所需流速率均已指定。由于网络资源有限，并非所有用户流都能成功计算出可行路径。我们希望你提供一个得分最高的解决方案。

注意：

• 所有边均为无向边，因此流可在两个方向上任意传输；
• 每条边既有容量（capacity），也有长度（称为 distance）；
• 多个流可共享同一条边；
• 多个流可在同一条边上同时沿相反方向传输；
• 就本题而言，卫星与地面基站并无本质区别，因此流可在抵达目标基站前，途经多个地面基站。

约束条件

1. 每条边的容量有限：一条边上承载的所有流的总速率（含两个方向）不得超过该边的容量；
2. 计算所得的流路径中不允许存在环路或回路；
3. 受卫星硬件限制，经过任一节点（包括源节点和目标节点）的流数量（即经过该节点的流数）不得超过该节点的站点流限制（$\mathit{SFL}$）。$\mathit{SFL}$ 的值为 $200$；
4. 两个节点之间可能存在多条平行边，这些边可能属于不同组。每组内的链路由节点上的同一芯片管理，并受组流限制（$\mathit{GFL}$）约束：一组内所有边上承载的不同流的总数不得超过该组的 $\mathit{GFL}$。$\mathit{GFL}$ 的值为 $100$；
5. 默认情况下，每个节点内部所有边彼此连通；但存在若干受限边对——即在指定节点内部，某些边对彼此之间无法通信；
6. 每 $5$ 分钟时间间隔内，最多允许提交 $2$ 次。

The first line contains four integers separated by space: $\mathit{NodeCount}$, $\mathit{EdgeCount}$, $\mathit{ConstrainedCount}$, and $\mathit{FlowCount}$.

• $8 \le \mathit{NodeCount} \le 1400$,
• $15 \le \mathit{EdgeCount} \le 15000$,
• $3 \le \mathit{ConstrainedCount} \le 3600$,
• $1 \le \mathit{FlowCount} \le 14000$.

The next $\mathit{EdgeCount}$ lines contain information about the network. Each line contains six integers: $\mathit{EdgeID}$, $\mathit{GroupID}$, $\mathit{StartNodeID}$, $\mathit{EndNodeID}$, $\mathit{Distance}$, and $\mathit{Capacity}$.

• $0 \le \mathit{EdgeID} \lt \mathit{EdgeCount}$,
• $0 \le \mathit{GroupID} \le 4500$,
• $0 \le \mathit{StartNodeID}, \mathit{EndNodeID} \lt \mathit{NodeCount}$,
• $\mathit{StartNodeID} \ne \mathit{EndNodeID}$,
• $100 \le \mathit{Distance} \le 10000$,
• $1 \lt \mathit{Capacity} \le 10^5$.

It's guaranteed that only multiple edges may share the same $\mathit{GroupID}$.

The next $\mathit{ConstrainedCount}$ lines contain information about the edge pairs that are not connected in the specified nodes of the network. All other edges are connected to each other by default. Each line contains three integers: $\mathit{NodeID}$, $\mathit{EdgeID}_1$, and $\mathit{EdgeID}_2$.

• $0 \le \mathit{NodeID} \lt \mathit{NodeCount}$,
• $0 \le \mathit{EdgeID}_1, \mathit{EdgeID}_2 \lt \mathit{EdgeCount}$,
• $\mathit{EdgeID}_1 \ne \mathit{EdgeID}_2$.

The next $\mathit{FlowCount}$ lines contain information about the flows to be calculated. Each line contains four integers: $\mathit{FlowID}$, $\mathit{SourceNode}$, $\mathit{TargetNode}$, and $\mathit{FlowRate}$.

• $0 \le \mathit{FlowID} \lt \mathit{FlowCount}$,
• $0 \le \mathit{SourceNode}, \mathit{TargetNode} \lt \mathit{NodeCount}$,
• $\mathit{SourceNode} \ne \mathit{TargetNode}$,
• $2 \le \mathit{FlowRate} \le 12000$

Don't forget that the $\mathit{SFL}$ and $\mathit{GFL}$ mentioned above are also important parameters.

For the simplicity, both $\mathit{EdgeID}$ and $\mathit{FlowID}$ of the $i$-th ($0$-indexed) edge (flow) is always equal to $i$.

第一行包含四个以空格分隔的整数：$\mathit{NodeCount}$、$\mathit{EdgeCount}$、$\mathit{ConstrainedCount}$ 和 $\mathit{FlowCount}$。

• $8 \le \mathit{NodeCount} \le 1400$，
• $15 \le \mathit{EdgeCount} \le 15000$，
• $3 \le \mathit{ConstrainedCount} \le 3600$，
• $1 \le \mathit{FlowCount} \le 14000$。

接下来的 $\mathit{EdgeCount}$ 行描述网络中的边信息。每行包含六个整数：$\mathit{EdgeID}$、$\mathit{GroupID}$、$\mathit{StartNodeID}$、$\mathit{EndNodeID}$、$\mathit{Distance}$ 和 $\mathit{Capacity}$。

• $0 \le \mathit{EdgeID} \lt \mathit{EdgeCount}$，
• $0 \le \mathit{GroupID} \le 4500$，
• $0 \le \mathit{StartNodeID}, \mathit{EndNodeID} \lt \mathit{NodeCount}$，
• $\mathit{StartNodeID} \ne \mathit{EndNodeID}$，
• $100 \le \mathit{Distance} \le 10000$，
• $1 \lt \mathit{Capacity} \le 10^5$。

保证仅有多重边可能共享相同的 $\mathit{GroupID}$。

接下来的 $\mathit{ConstrainedCount}$ 行描述网络中指定节点上不连通的边对信息。其余所有边默认彼此连通。每行包含三个整数：$\mathit{NodeID}$、$\mathit{EdgeID}_1$ 和 $\mathit{EdgeID}_2$。

• $0 \le \mathit{NodeID} \lt \mathit{NodeCount}$，
• $0 \le \mathit{EdgeID}_1, \mathit{EdgeID}_2 \lt \mathit{EdgeCount}$，
• $\mathit{EdgeID}_1 \ne \mathit{EdgeID}_2$。

接下来的 $\mathit{FlowCount}$ 行描述待计算的流信息。每行包含四个整数：$\mathit{FlowID}$、$\mathit{SourceNode}$、$\mathit{TargetNode}$ 和 $\mathit{FlowRate}$。

• $0 \le \mathit{FlowID} \lt \mathit{FlowCount}$，
• $0 \le \mathit{SourceNode}, \mathit{TargetNode} \lt \mathit{NodeCount}$，
• $\mathit{SourceNode} \ne \mathit{TargetNode}$，
• $2 \le \mathit{FlowRate} \le 12000$。

请勿忘记，前述提到的 $\mathit{SFL}$ 和 $\mathit{GFL}$ 同样是重要参数。

为简化起见，第 $i$ 个（$0$-索引）边（流）的 $\mathit{EdgeID}$（$\mathit{FlowID}$）恒等于 $i$。

In the first line, output the number of your success flows.

Next, each line output edge information about the path that a flow passes through.

The format is as follows: $\mathit{FlowID}\ \mathit{EdgeID}_1\ \mathit{EdgeID}_2\ \mathit{EdgeID}_3\ \dots\ \mathit{EdgeID}_n$.

There is no requirement on the output sequence between flow paths, but edges in one flow must be outputted in order, from source node to target node. Please output all successfully calculated flow paths. For other flows that are not output, the checker determines that you have not found appropriate paths for the flows by default.

第一行输出成功流的数量。

接下来，每一行输出一条流所经过的边的信息。

格式如下：$\mathit{FlowID}\ \mathit{EdgeID}_1\ \mathit{EdgeID}_2\ \mathit{EdgeID}_3\ \dots\ \mathit{EdgeID}_n$。

不同流路径之间的输出顺序没有要求，但同一条流中的边必须按从源节点到目标节点的顺序输出。请输出所有成功计算出的流路径。对于未输出的其他流，评测器默认认为你未能为其找到合适的路径。

The total distance of a flow path is $620$ ($120 + 100 + 100 + 300 = 620$). (Note: 0 9 10 12 13 is also a valid output result.)

流路径的总距离为 $620$（$120 + 100 + 100 + 300 = 620$）。（注意：0 9 10 12 13 也是一个有效的输出结果。）