{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"BIT最近接收到了他们的新超级计算机,这是一台32处理器的Apollo Odyssey分布式共享内存机器,带有分层通信子系统。瓦伦泰恩·麦基的研究导师杰克·斯威格特要求她对这台新系统进行基准测试。\r\u003cbr\u003e“由于Apollo是一台分布式共享内存机器,内存访问和通信时间并不均匀,”瓦伦泰恩告诉斯威格特。“处理器之间共享相同内存子系统的通信速度很快,但处理器之间如果不在同一子系统上通信速度就会慢一些。Apollo和我们实验室中的机器之间的通信速度更慢。”\r\u003cbr\u003e\r\u003cbr\u003e“Apollo的消息传递接口(MPI)的端口工作得怎么样?”斯威格特问道。\r\u003cbr\u003e\r\u003cbr\u003e“不太好,”瓦伦泰恩回答。“要从一个处理器向其他所有n-1个处理器广播消息,他们只是进行一系列的n-1次发送。这实际上使事情变得串行化并降低了性能。”\r\u003cbr\u003e\r\u003cbr\u003e“有什么办法可以解决这个问题吗?”\r\u003cbr\u003e\r\u003cbr\u003e“有的,”瓦伦泰恩微笑着说。“有的。一旦第一个处理器将消息发送给另一个处理器,这两个处理器就可以同时向另外两个主机发送消息。然后就会有四个主机可以发送消息,以此类推。”\r\u003cbr\u003e\r\u003cbr\u003e“啊,所以你可以将广播作为二叉树来实现!”\r\u003cbr\u003e\r\u003cbr\u003e“不完全是二叉树——我们的网络有一些特定的特性可以利用。我们拥有的接口卡允许每个处理器同时向连接到它的任意数量的其他处理器发送消息。然而,消息不一定会同时到达目的地——这涉及到通信成本。总的来说,我们需要考虑网络拓扑中每条链路的通信成本,并相应地规划以最小化进行广播所需的总时间。”"}},{"title":"输入","value":{"format":"HTML","content":"输入将描述连接n个处理器的网络拓扑。输入的第一行将是n,处理器的数量,满足1 \u003c\u003d n \u003c\u003d 100。\r\u003cbr\u003e\r\u003cbr\u003e输入的其余部分定义了一个邻接矩阵A。邻接矩阵是方阵,大小为n x n。它的每个条目将是一个整数或字符x。A(i,j)的值表示从节点i直接发送消息的费用。A(i,j)的值为x表示不能直接从节点i发送消息到节点j。\r\u003cbr\u003e\r\u003cbr\u003e请注意,节点向自身发送消息不需要网络通信,因此对于1 \u003c\u003d i \u003c\u003d n,A(i,i) \u003d 0。另外,您可以假设网络是无向的(消息可以双向传递且开销相等),因此A(i,j) \u003d A(j,i)。因此,只会提供A的(严格)下三角部分的条目。\r\u003cbr\u003e\r\u003cbr\u003e您的程序的输入将是A的下三角部分。也就是说,输入的第二行将包含一个条目,A(2,1)。接下来的一行将包含两个条目,A(3,1)和A(3,2),依此类推。"}},{"title":"输出","value":{"format":"HTML","content":"您的程序应输出从第一个处理器向所有其他处理器广播消息所需的最短通信时间。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n50\r\n30 5\r\n100 20 50\r\n10 x x 10\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e35\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}