2021 ICPC Communication Routing Challenge: Marathon 中文翻译

andychen_2012 · 2021-10-09 13:32:14 · 个人记录

现在有一个光通信网络，你要通过规划路径提高通信资源利用率。下图是一个卫星间光通信网络。

用户消息从一个地面基站（节点4至7）发送，并通过空间中的卫星（节点0至3）传输到另一个地面基站（节点4至7）。

上图中，基站和卫星称为节点，每一个节点之间都存在通信连接，称为边。

用户消息在边上传输，称为流。每个用户的流量（即消息流量）不同。

两个节点之间会有很多平行边（例如边0,1,2），每条边的容量和传输距离也不同。

容量越大，可以传输的用户消息越多；传输距离越短，延迟越低，通信质量越好。

节点也有其内部的结构。节点的某些边无法相互通信，因为它们未完全连接。例如边7和边5不能相互通信，因为它们受到了节点2的约束，因此流不能通过两条未连接的边通过节点2。

下图是节点2的内部结构。

现在，在输入网络中，指定了每个用户流的源节点、目标节点和所需的流量。

由于网络资源有限，可能无法成功计算所有用户流的路径。我们希望您能提供得分最高的解决方案。

请注意：

• 所有的边缘都是无向的，所以流可能会向两个方向流动，

• 边具有容量和长度（命名为distance），

• 多个流可能使用同一条边，

• 流可能同时以相反方向通过同边缘，

• 为了解决这个问题，卫星和基站之间没有区别，因此在到达目的站之前，流量可能会经过多个基站。

约束条件：

1.每个边的容量都是有限的。边承载的所有流量的总速率不得超过边的容量。容量限制了两个方向的总流量。

2.计算出来的路径不允许循环，即不允许从节点a出发回到节点a。

3.由于卫星内部的硬件限制，通过节点（包括源节点和目标节点）的流量数量不能超过站点流量限制（SFL），SFL=200

4.两个节点之间有多条平行边，它们可能属于不同的组。每个组中的链路由节点上的同一芯片管理，并且存在组流限制（GFL）。组中所有边上的通信总数不能超过组的GFL。GFL的值为100

5.默认情况下，每个节点中的所有边都彼此连接。但也有一些受约束的边对，即指定节点内无法相互通信的边对。

6.你最多可以在每五分钟内提交两次。

输入：

第一行包含四个整数：节点数量(NodeCount)、边数(EdgeCount)、限制边的条数（ConstrainedCount）、流的数量

• 8≤NodeCount≤1400,
• 15≤EdgeCount≤15000,
• 3≤ConstrainedCount≤3600,
• 1≤FlowCount≤14000.

接下来EdgeCount行包括了网络信息。每一行包括六个整数：边的ID(EdgeID)、归属的组的ID(GroupID)、开始节点的ID(StartNodeID)、结束节点的ID(EndNodeID)、距离(Distance)、容量(Capacity)

• 0≤EdgeID<EdgeCount,
• 0≤GroupID≤4500,
• 0≤StartNodeID,EndNodeID<NodeCount,
• StartNodeID≠EndNodeID,
• 100≤Distance≤10000,
• 1<Capacity≤105.

可以保证只有多条边可以共享同一个组。

接下来ConstrainedCount行包含有关在网络的指定节点中未连接的边对的信息。默认情况下，所有其他边都彼此连接。每行包含三个整数：点的ID（NodeID）、指定的两条边EdgeID1和EdgeID2。

接下来FlowCount行包含了要计算的流的信息，每一行有四个整数：流的编号（FlowID）、源节点的编号（SourceNode）、目标节点的编号（TargetNode）、流量（FlowRate）

别忘了SFL和GFL,它们也是重要的参数。

为了简单起见，第i条的边或流的EdgeID或FlowID总是与i相等。

输出：

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

接下来，每行输出关于流通过的路径的边缘信息。 格式如下：

FlowID EdgeID1 EdgeID2 EdgeID3…EdgeIDn.

流路径之间的输出顺序没有要求，但一个流中的边必须按顺序从源节点输出到目标节点。

请输出所有成功计算的流路径。对于未输出的其他流，默认情况下，检查器确定您未找到流的适当路径。

分数计算：