← 返回题目列表

Codeforces · 1576/A

A. 通信路由挑战

中文机器翻译题面 查看原题

在光通信网络中,适当的路径规划可以提高通信资源的利用率,给用户带来流畅的通信体验。下图所示为星间光通信网络。用户消息从一个地面基站(节点$$$4$$$至$$$7$$$)发送,并通过太空中的卫星(节点$$$0$$$至$$$3$$$)传输至另一地面基站(节点$$$4$$$至$$$7$$$)。

上图中,基站与卫星之间、卫星与卫星之间都有通信连接(简称边缘)。基站和卫星称为节点。

用户消息在这些边缘上传输并称为流。有些用户可能会与朋友进行视频通话,有些用户可能会向家人发送短信。因此,每个用户的消息流量(称为流量)是不同的。

两个节点之间存在许多条平行边(例如边 $$$0$$$、$$$1$$$ 和 $$$2$$$),并且每条边的容量也不同。容量越大,可以传输的用户消息越多;传输距离越短,延迟越低,通信质量越好。

节点也有其内部结构。如下所示,节点内部的某些边无法相互通信,因为这些边(约束边对)未完全连接。例如,节点$$$2$$$内部的边$$$5$$$和边$$$7$$$无法相互通信,因此流无法通过遍历这两条不连接的边来通过节点$$$2$$$。

现在,在输入网络中,指定了每个用户流的源节点、目标节点和所需的流量。由于网络资源有限,可能无法成功计算所有用户流的路径。我们希望您能够提供最高分的解决方案。

请注意,

- 所有边都是无向的,因此流量可能来自两个方向,
- 边具有容量和长度(命名距离),
- 多个流可以使用相同的边,
- 流量可能同时以相反方向穿过同一边缘,
- 就该问题而言,卫星和基站之间没有区别,因此流量在到达目的地站之前可能会经过多个基站。

约束

1. 每条边的容量有限。一条边承载的所有流量的总速率不能超过该边的容量。容量限制了两个方向的总流量。
2. 计算的流路不允许出现环路或循环。
3. 由于卫星内部硬件限制,经过节点(包括源节点和目标节点)的流量不能超过该节点的站点流量限制($$$\mathit{SFL}$$$)。 $$$\mathit{SFL}$$$ 的值为 $$$200$$$。
4. 两个节点之间存在多条平行边,这些边可能属于不同的组。每个组中的链路由节点上的同一芯片管理,并且有组流量限制($$$\mathit{GFL}$$$)。组中所有边上的不同流的总数不能超过该组的$$$\mathit{GFL}$$$。 $$$\mathit{GFL}$$$ 的值为 $$$100$$$。
5. 默认情况下,每个节点中的所有边都相互连接。但有一些受约束的边对——指定节点内无法相互通信的边对。
6. 每 $$$5$$$ 分钟间隔内提交的内容不得超过 $$$2$$$。

输入

第一行包含四个由空格分隔的整数:$$$\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} < \mathit{EdgeCount}$$$,
- $$$0 \le \mathit{GroupID} \le 4500$$$,
- $$$0 \le \mathit{StartNodeID}, \mathit{EndNodeID} < \mathit{NodeCount}$$$,
- $$$\mathit{StartNodeID} \ne \mathit{EndNodeID}$$$,
- $$$100 \le \mathit{距离} \le 10000$$$,
- $$$1 < \mathit{容量} \le 10^5$$$。

保证只有多条边可以共享相同的$$$\mathit{GroupID}$$$。

接下来的 $$$\mathit{ConstrainedCount}$$$ 行包含有关网络指定节点中未连接的边对的信息。默认情况下,所有其他边都相互连接。每行包含三个整数:$$$\mathit{NodeID}$$$、$$$\mathit{EdgeID}_1$$$ 和 $$$\mathit{EdgeID}_2$$$。

- $$$0 \le \mathit{NodeID} < \mathit{NodeCount}$$$,
- $$$0 \le \mathit{EdgeID}_1, \mathit{EdgeID}_2 < \mathit{EdgeCount}$$$,
- $$$\mathit{EdgeID}_1 \ne \mathit{EdgeID}_2$$$。

接下来的 $$$\mathit{FlowCount}$$$ 行包含有关要计算的流量的信息。每行包含四个整数:$$$\mathit{FlowID}$$$、$$$\mathit{SourceNode}$$$、$$$\mathit{TargetNode}$$$ 和 $$$\mathit{FlowRate}$$$。

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

别忘了上面提到的 $$$\mathit{SFL}$$$ 和 $$$\mathit{GFL}$$$ 也是重要的参数。

为简单起见,$$$i$$$($$$0$$$索引)边(流)的 $$$\mathit{EdgeID}$$$ 和 $$$\mathit{FlowID}$$$ 始终等于 $$$i$$$。

输出

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

接下来,每行输出有关流经过的路径的边缘信息。

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

流路径之间的输出顺序没有要求,但一个流中的边必须按顺序输出,从源节点到目标节点。请输出所有成功计算的流路。对于其他未输出的流,检查器默认情况下会确定您尚未找到适合这些流的路径。

示例

输入 #1

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

1
0 8 0 3 13

注意

评分:
1. 违反约束、超时或超出内存限制的解决方案无效。
2. 根据公式 $$$\mathit{Score}=\mathit{SuccessFlowNum}+\max \left(1-\left(\frac{\mathit{AvgDistance}}{1000000}\right),0\right)$$$,得分较高的解获胜。 (也就是说,具有更多成功规划的流路径的解决方案获胜。如果两个解决方案具有相同数量的成功规划的流路径,则平均路径距离较小的解决方案获胜。具有 $$$0$$$ 流路径的输出将被视为不正确。)
3. 如果两个解决方案得分相同,则先提交的解决方案获胜。
4. 对于多项测试,根据所有测试的总和进行排名。如果该溶液在任何一次测试中都没有结果,则记录为整体无结果。
5. 在您多次提交的作品中,得分最高的为最终得分。
6. 检查器仅在一个 CPU 核心上运行您的解决方案,因此多线程实现不会带来任何利润。
7. 每 $$$5$$$ 分钟间隔内提交的内容不得超过 $$$2$$$。

流路的总距离为 $$$620$$$ ($$$120 + 100 + 100 + 300 = 620$$$)。 (注:0 9 10 12 13也是有效的输出结果。)