UVa 423 MPI Maelstrom

题目描述题目要求计算从第一个处理器向所有其他处理器广播消息所需的最短时间。给定nnn个处理器之间的通信延迟以邻接矩阵形式给出消息可以通过中间处理器转发且每个处理器可以同时向多个其他处理器发送消息。需要找出从处理器111到所有其他处理器的最短路径中的最大值即广播完成所需的最短时间。输入格式第一行一个整数nnn1≤n≤1001 \le n \le 1001≤n≤100表示处理器的数量。接下来若干行输入邻接矩阵的下三角部分不含对角线。具体格式为第222行包含A2,1A_{2,1}A2,1​第333行包含A3,1A_{3,1}A3,1​和A3,2A_{3,2}A3,2​第444行包含A4,1A_{4,1}A4,1​、A4,2A_{4,2}A4,2​和A4,3A_{4,3}A4,3​依此类推直到第nnn行包含An,1A_{n,1}An,1​到An,n−1A_{n,n-1}An,n−1​每个条目为一个整数表示通信延迟或字符x表示不能直接通信。输入保证网络是无向的即Ai,jAj,iA_{i,j} A_{j,i}Ai,j​Aj,i​且Ai,i0A_{i,i} 0Ai,i​0。输出格式输出一个整数表示从处理器111向所有其他处理器广播消息所需的最短时间。样例输入5 50 30 5 100 20 50 10 x x 10输出35题目分析本题的核心是计算从源节点处理器111到所有其他节点的最短路径然后取这些路径长度的最大值。由于消息可以同时沿多条路径转发广播完成的时间取决于最慢的那条路径。问题转化给定nnn个节点的无向图每条边有权重通信延迟节点iii到节点jjj不可达时权重视为无穷大。需要计算answermax⁡2≤j≤ndist(1,j) \text{answer} \max_{2 \le j \le n} \text{dist}(1, j)answer2≤j≤nmax​dist(1,j)其中dist(1,j)\text{dist}(1, j)dist(1,j)为节点111到节点jjj的最短路径长度。算法选择由于n≤100n \le 100n≤100可以使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法O(n3)O(n^3)O(n3)计算所有节点对之间的最短路径然后取第一行的最大值。也可以使用Dijkstra\texttt{Dijkstra}Dijkstra算法O(n2)O(n^2)O(n2)或O((nm)log⁡n)O((n m) \log n)O((nm)logn)从源节点计算单源最短路径。考虑到输入规模较小两种方法均可。输入解析输入只给出了邻接矩阵的下三角部分。需要正确读取这些值并构建对称的邻接矩阵对于iji jij读取值Ai,jA_{i,j}Ai,j​。若值为x则Ai,jAj,i∞A_{i,j} A_{j,i} \inftyAi,j​Aj,i​∞不可达。否则Ai,jAj,i读入的整数A_{i,j} A_{j,i} \text{读入的整数}Ai,j​Aj,i​读入的整数。对角线元素Ai,i0A_{i,i} 0Ai,i​0。最短路径计算使用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法初始化dist[i][j]∞\textit{dist}[i][j] \inftydist[i][j]∞dist[i][i]0\textit{dist}[i][i] 0dist[i][i]0。对于每条边(u,v,w)(u, v, w)(u,v,w)设置dist[u][v]dist[v][u]w\textit{dist}[u][v] \textit{dist}[v][u] wdist[u][v]dist[v][u]w。三重循环更新dist[i][j]min⁡(dist[i][j],dist[i][k]dist[k][j])\textit{dist}[i][j] \min(\textit{dist}[i][j], \textit{dist}[i][k] \textit{dist}[k][j])dist[i][j]min(dist[i][j],dist[i][k]dist[k][j])。计算完成后dist[1][j]\textit{dist}[1][j]dist[1][j]即为节点111到节点jjj的最短距离。结果输出max⁡j1ndist[1][j]\max_{j1}^{n} \textit{dist}[1][j]maxj1n​dist[1][j]dist[1][1]0\textit{dist}[1][1] 0dist[1][1]0不影响最大值。复杂度分析Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall时间复杂度O(n3)106O(n^3) 10^6O(n3)106n≤100n \le 100n≤100时完全可接受。代码实现// MPI Maelstrom// UVa ID: 423// Verdict: Accepted// Submission Date: 2016-07-17// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constlonglongMAX_TIMESnumeric_limitsint::max();intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);longlongn,times[110][110];while(cinn){for(inti1;in;i)for(intj1;jn;j)times[i][j]MAX_TIMES;string digits;for(inti1;in;i)for(intj1;ji-1;j){cindigits;if(digitsx)continue;else{times[i][j]stoll(digits);times[j][i]times[i][j];}}for(inti1;in;i)times[i][i]0;for(intk1;kn;k)for(inti1;in;i)for(intj1;jn;j)if(times[i][j]times[i][k]times[k][j])times[i][j]times[i][k]times[k][j];// from THE first node to another NODElonglongmax_delay0;for(intj1;jn;j)max_delaymax(max_delay,times[1][j]);coutmax_delay\n;}return0;}