MPI Maelstrom

BIT最近交付了他们的新超级计算机，一台32处理器的阿波罗奥德赛（Apollo Odyssey）分布式计算机 （分布式计算机系统是将多台小型微型机互连组成的一种新型计算机系统...详情自行百度）。 具有分层通信子系统的共享内存机。瓦伦丁·麦基（Valentine McKee）的研究顾问杰克·斯威格特（Jack Swigert）要求她对新系统进行基准测试。 “由于Apollo是一个分布式共享内存机，因此内存访问和通信时间不统一，” 瓦伦丁告诉斯威格特。“共享处理器之间的通信速度很快，而同一个内存子系统，但不在同一子系统上的处理器之间的速度较慢。阿波罗号和我们实验室的机器之间的通讯还很慢。” “Apollo的消息传递接口（MPI）端口是如何工作的？”斯威格特问。“不太好，”瓦伦丁回答。“从一个处理器向所有其他n-1处理器，它们只是执行n-1发送的序列。这真的是连载和杀戮表演。”“你能做些什么来解决这个问题吗？““是的，”瓦伦丁笑着说。“一旦第一个处理器将消息发送给另一个处理器， 然后，两个可以同时向其他两个主机发送消息。那么会有四个主机可以发送，等等。” “啊，所以你可以用二叉树来做广播！”“不是真正的二叉树-我们的网络有一些我们应该利用的特殊特性。我们拥有的接口卡允许每个处理器同时向任意数量的与之相连的其他处理器。但是，消息不一定到达目的地。同时，还涉及到通信成本。一般来说，我们需要考虑我们的网络拓扑结构中每个链路的通信成本，并相应地计划将进行广播所需的总时间。” (都是废话qwq） 输入： 输入的第一行为n（处理器的数量），1<=n<=100。 输入的其余部分(2..n+1行）邻接矩阵A是方形的，大小为n×n。 每行都是整数或字符“x”。A（i，j）的值是直接从节点i向节点j发送消息的费用。 A（i，j）的值为“x”表示消息不能直接从节点I发送到节点J。 注意，对于向其自身发送消息的节点，不需要网络通信，因此对于 1 <= i <= n 有a（i，i）=0 而且网络是无向的（消息可以向任意方向移动，开销相等），即a（i，j）=a（j，i）。 程序的输入将是A（对称矩阵）的（左下）三角形部分 即A的第二行为A（2,1）的值（即 2<-->1 的权值）。 再下一行将包含两个数，一个（3,1）的值和一个（3,2）的值，依此类推。 （简单来讲：这是个矩阵，然后因为是无向图，所以矩阵是对称的，输入第一行给出矩阵大小n，然后2到n+1行就是矩阵的值，而且只给出半个矩阵的值（毕竟对称），用样例来讲： 1 2 3 4 5 1 0 50 30 100 10 2 50 0 5 x x 3 30 5 0 50 x 4 100 20 50 0 10 5 10 x x 10 0 以00000为对称轴，输入的2至n+1行给出左下半个矩阵的值 输出： 输出从其它所有处理器到第一个处理器的广播消息所需的最短总通信时间。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=364 [PDF](https://uva.onlinejudge.org/external/4/p423.pdf) 



5
50
30 5
100 20 50
10 x x 10

35