MBone
描述
MBone是“Multicast Backbone”（多播骨干网）的缩写。它是建立在互联网协议之上的虚拟网络的实现。与面向连接的数据传输（单播）和从发送者到网络中所有目的地的传输（广播）不同，MBone提供了多播功能，即向所有加入“多播组”的主机发送数据的能力。组的所有成员都可以向组发送数据并从组接收数据。
你的程序需要模拟一个简化版的MBone。在我们的设定中，MBone由多播路由器和主机组成，每个主机属于一个路由器。一个路由器及其所属的主机称为一个“岛屿”。路由器之间通过隧道连接，隧道是简单的通信通道：从一端发送的数据包会在另一端接收。
为了加入一个多播组，主机必须向其对应的多播路由器发送一个协议消息，指定它想要加入的组的地址。这样，该主机将接收发送到该组的所有数据包。
为了向多播组发送数据包，主机将数据包发送到其所在岛屿的多播路由器。每个多播路由器会复制所有接收到的数据包，并通过其每个出站隧道发送。然后，它将数据包的副本发送给岛屿上所有已加入该组的主机。
数据包在MBone中的分发范围通过一个称为TTL（Time To Live，生存时间）的整数值来限制。每个数据包都有一个TTL值。如果数据包通过隧道发送，其TTL会减去该隧道的阈值（一个整数值）。如果数据包的TTL小于隧道的阈值，则不会通过该隧道发送。
输入
程序的输入将包含多个MBone网络的描述。每个描述的第一部分定义了网络拓扑，第二部分描述了该网络上的活动。
-
第一部分的第一行包含一个整数m（1 < m ≤ 10），表示网络中的岛屿数量。m = 0表示输入结束。接下来的几行包含m个岛屿的描述。
- 每个岛屿描述的第一行是多播路由器的名称（最多20个非空字符的字符串），后跟一个整数，表示岛屿描述中剩余的行数。这些行可以是以下两种类型之一：
- 属于岛屿的主机：
H <主机地址> - 隧道：
T <阈值> <目标名称>
<主机地址>和<阈值>是正整数，分别指定主机的地址和隧道的阈值。<目标名称>是隧道另一端的目标路由器的名称，该名称始终与当前路由器不同。
- 属于岛屿的主机：
- 每个岛屿描述的第一行是多播路由器的名称（最多20个非空字符的字符串），后跟一个整数，表示岛屿描述中剩余的行数。这些行可以是以下两种类型之一：
-
第二部分的第一行包含一个不超过1000的整数，表示接下来的活动描述的行数。每行描述一个主机的活动：
- 加入组：
J <主机地址> <组地址> - 离开组：
L <主机地址> <组地址> - 向组发送数据包：
S <主机地址> <组地址> <数据包ID> <TTL>
<组地址>、<数据包ID>和<TTL>是正整数，含义显而易见。- 路由器名称、主机地址和数据包ID在同一个场景中都是唯一的。
- 数据包的TTL最多为1000。
- 网络中最多有50个主机和100条隧道，任何时候最多有20个活跃组（即至少有一个主机成员的组）。
- 主机不会尝试离开它未加入的组，也不会尝试加入它已加入的组。
- 加入组：
输出
在输出中，你需要为每个场景打印网络中主机接收到的数据包。如果主机接收到多个副本的数据包（通过不同路径路由），它们只保留TTL最高的副本（通过“最短”路径到达）。
对于每个网络描述：
- 首先输出网络编号，如示例所示。
- 随后的每行格式为：
<主机地址> <数据包ID> <TTL>- 表示主机
<主机地址>接收到了ID为<数据包ID>、剩余TTL为<TTL>的数据包。 - 行的三个条目之间用单个空格分隔。
- 表示主机
- 输出必须按升序排序：首先按主机地址，其次按数据包ID。
- 每个测试用例后输出一个空行。
示例输入 1
3
Nuremberg 3
T 8 Munich
H 3768
H 3669
Munich 6
H 721
H 722
H 723
T 6 Nuremberg
H 857
T 9 Ulm
Ulm 5
H 51225
H 51226
H 51227
T 15 Nuremberg
T 9 Munich
14
J 51227 26
J 3768 27
J 723 26
J 3768 26
S 3768 26 1000 17
J 857 26
S 3768 26 320 16
J 722 26
L 857 26
S 51227 26 1001 37
S 723 26 533 5
L 51227 26
L 3768 27
L 723 26
0
示例输出 1
Network #1
722 533 5
722 1001 28
723 320 8
723 533 5
723 1000 9
723 1001 28
857 320 8
3768 320 16
3768 1000 17
3768 1001 22
51227 1000 0
51227 1001 37
来源
1997年西南欧区域赛