题意分析

题目描述了一个由$n$个处理器组成的网络，每个处理器之间的通信时间不同（用邻接矩阵表示）。要求计算从第一个处理器（源点）广播消息到所有其他处理器所需的最小总时间。

• 输入：

  • 第一行是$n$（$1 \leq n \leq 100$），表示处理器数量。
  • 接下来的$n-1$行给出邻接矩阵的严格下三角部分，$A(i,j)$表示$i$到$j$的通信时间（$x$表示不可达）。
  • 由于网络是无向的，$A(i,j) = A(j,i)$，且$A(i,i) = 0$。

• 输出：

  • 从节点$1$到所有其他节点的最短路径中的最大值（即广播完成的最短时间）。

解题思路

本题可以转化为单源最短路径问题，使用Dijkstra算法求解：

1. 初始化：
   • 用邻接矩阵存储图的边权，不可达的边权设为$INF$（无穷大）。
   • 初始化$dist$数组，记录源点（节点$1$）到各节点的最短距离。
2. Dijkstra算法：
   • 每次选择当前未被访问且距离源点最近的节点$u$。
   • 更新$u$的邻居节点的$dist$值（松弛操作）。
3. 结果计算：
   • 广播完成时间取决于$dist$数组中的最大值（即最晚收到消息的节点）。

实现步骤

1. 输入处理：
   • 读取$n$，初始化邻接矩阵（对角元为$0$，其余初始为$INF$）。
   • 读取下三角部分，处理字符$x$（不可达），并填充对称位置。
2. Dijkstra算法：
   • 初始化$dist$数组为源点到各点的直接距离。
   • 每次选择未访问的最近节点，松弛其邻居。
3. 输出结果：
   • 遍历$dist$数组，输出最大值。

C++实现

#include <iostream>
#include <cstdio>
#include <cstring> // 替换 memory.h
#define INF 9999999
using namespace std;

int visited[105]; // 标记是否访问
int map[105][105]; // 标记节点到节点之间的距离
int dist[105]; // 记录到源点距离的数组
int N;

int Dijkstra() {
    int i, j, min, pos, max;
    memset(visited, 0, sizeof(visited));

    for (i = 1; i <= N; i++)
        dist[i] = map[1][i]; // 初始化所有节点的 dist[] 数组为其到源点的距离

    visited[1] = 1;

    for (i = 1; i <= N; i++) {
        min = INF;
        for (j = 1; j <= N; j++) {
            if (!visited[j] && dist[j] < min) { // 找到一个距离源点最近的节点
                pos = j;
                min = dist[j];
            }
        }

        if (min == INF) break; // 如果 min=INF 表示源点到所有其他节点都不可达

        visited[pos] = 1; // 标记 pos 节点为已访问的节点

        for (j = 1; j <= N; j++) {
            // 如果 i 节点经由 pos 节点到达 j 节点的距离小于 i 节点直接到 j 节点的距离（即 i->pos->j 的距离小于 i->j 的距离）, 则更新 j 节点的 dist[j] 值
            if (!visited[j] && dist[pos] + map[pos][j] < dist[j])
                dist[j] = dist[pos] + map[pos][j];
        }
    }

    max = 0;
    for (i = 1; i <= N; i++) {
        if (dist[i] > max)
            max = dist[i];
    }

    return max;
}

int main() {
    int i, j, temp;
    char cost[10];

    while (cin >> N) {
        for (i = 1; i <= N; i++) // 初始化 map[][] 数组，节点到自身的距离设为 0
            for (j = 1; j <= N; j++)
                if (i == j) map[i][j] = 0;

        for (i = 2; i <= N; i++) {
            getchar();
            for (j = 1; j <= i - 1; j++) {
                scanf("%s", cost); // 输入 cost 字符数组
                if (cost[0] == 'x') {
                    map[i][j] = map[j][i] = INF;
                } else {
                    sscanf(cost, "%d", &temp); // sscanf 表示从字符串中格式化输入，temp 为整型的 cost
                    map[i][j] = temp;
                    map[j][i] = temp;
                }
            }
        }

        cout << Dijkstra() << endl;
    }
    return 0;
}

代码说明

• 输入处理：
  • 使用sscanf将字符串转换为整数，处理字符x。
  • 邻接矩阵对称填充（无向图）。
• Dijkstra算法：
  • dist数组记录最短路径，visited数组标记已访问节点。
  • 每次选择最近的未访问节点，更新其邻居的dist值。
• 结果输出：
  • dist数组的最大值即为广播完成时间。

时间复杂度：$O(n^2)$，适用于$n \leq 100$的规模。

##算法标签 图结构, 最短路, Dijstra, Floyd

题目描述

BIT最近购入了一台新的超级计算机——一台具有32个处理器的Apollo Odyssey分布式共享内存机器，并配备了分层通信子系统。Valentine McKee的研究导师Jack Swigert要求她对这台新机器进行基准测试。

“由于Apollo是一台分布式共享内存机器，内存访问和通信时间并不均匀，” Valentine对Swigert说道，“在共享相同内存子系统的处理器之间通信速度较快，而在不同子系统的处理器之间通信速度较慢。而Apollo与实验室其他机器之间的通信速度更慢。”

“Apollo的消息传递接口（MPI）移植得怎么样了？” Swigert问道。

“不太理想，” Valentine回答，“当需要将一条消息从一个处理器广播到其余的$n-1$个处理器时，它们采用的是顺序执行$n-1$次发送操作的方法。这种方式会严重串行化传输过程，导致性能大幅下降。”

“你有什么办法可以改进吗？”

“当然，” Valentine微笑着说，“当第一个处理器将消息发送给另一个处理器后，这两个处理器就可以同时向另外两个处理器发送消息。这样一来，就会有四个处理器可以发送，接着是八个，依此类推。”

“哦，所以你是要用二叉树的方式来进行广播？”

“不完全是二叉树——我们的网络有一些特定的特性值得利用。我们的接口卡允许每个处理器同时向任何数量的已连接处理器发送消息。然而，消息不会同时到达目标处理器，因为存在通信代价。因此，我们需要考虑网络拓扑结构中每条通信链路的通信成本，并合理规划广播路径，以最小化完成整个广播所需的总时间。”

输入格式

输入描述网络拓扑结构，表示$n$个处理器之间的连接情况。

• 第一行是一个整数$n$，表示处理器的数量，满足 $1 \leq n \leq 100$。
• 接下来的部分定义了一个邻接矩阵$A$的下三角部分。该矩阵是一个$n \times n$的方阵，每个元素要么是一个整数，要么是字符x。
• $A(i, j)$ 表示从处理器 $i$ 直接向处理器 $j$ 发送消息的代价（$A(i, j)$ 的值）。
• 如果 $A(i, j)$ 为 x，表示 $i$ 不能直接向 $j$ 发送消息。
• 由于网络是无向的（消息传输的代价是对称的），所以 $A(i, j) = A(j, i)$。
• 由于自身发送不需要网络通信，所以 $A(i, i) = 0$（其中 $1 \leq i \leq n$）。
• 输入数据仅提供$A$的下三角部分，即：
  • 第二行输入 $A(2,1)$
  • 第三行输入 $A(3,1), A(3,2)$
  • 第四行输入 $A(4,1), A(4,2), A(4,3)$
  • 依此类推。

输出格式

程序应输出从处理器 $1$ 向所有其他处理器广播消息所需的最小通信时间。

输入示例 1

5
50
30 5
100 20 50
10 x x 10

输出示例 1

35

数据来源

East Central North America 1996

题意

N个处理器之前要传递信息，给出一个三角矩阵，记录map[i][j]距离，若为x则表示不能传递，问从第一个信息处理器到其他所有处理器距离的最大值。

参考代码

//POJ--1502:MPI Maelstrom    最短路径：Dijkstra算法 
#include<iostream> 
#include<stdio.h>
#include<string.h>
#include<memory.h>
#define INF 9999999
using namespace std;
 
int visited[105];//标记是否访问 
int map[105][105];//标记节点到节点之间的距离 
int dist[105];//记录到源地距离的数组 
int N;
 
int Dijkstra()
{
   int i,j,min,pos,max;
   memset(visited,0,sizeof(visited));
   
   for(i=1;i<=N;i++)
      dist[i]=map[1][i];//初始化所有节点的dist[]数组为其到源点的距离 
   
   visited[1]=1;
   
   for(i=1;i<=N;i++)
   {
      min=INF;
      for(j=1;j<=N;j++)
      {
         if(!visited[j]  && dist[j]<min)//找到一个距离源点最近的节点 
         {
            pos=j;
            min=dist[j];
         }
      }
      
      if(min==INF)   break;//如果min=INF表示源点到所有其他节点都不可达 
      
      visited[pos]=1;//标记pos节点为已访问的节点 
      
      for(j=1;j<=N;j++)
      {
         //如果i节点经由pos节点到达j节点的距离小于i节点直接到j节点的距离（即i->pos->j的距离小于i->j的距离）,则更新j节点的dist[j]值  
         if(!visited[j] && dist[pos]+map[pos][j]<dist[j])
            dist[j]=dist[pos]+map[pos][j];
      }     
   }
   
   max=0;
   
   for(i=1;i<=N;i++)
   {
      if(dist[i]>max)
         max=dist[i];
   }
   
   return max;
} 
 
int main()
{
    int i,j,temp;
    char cost[10];
    
    while(cin>>N)
    {
       for(i=1;i<=N;i++)//初始化map[][]数组，节点到自身的距离设为0 
          for(j=1;j<=N;j++)
             if(i==j)   map[i][j]=0;
       
       for(i=2;i<=N;i++)
       {
           getchar();
           for(j=1;j<=i-1;j++)
           {
              scanf("%s",cost);//输入cost字符数组 
              if(cost[0]=='x') 
              {
                 map[i][j]=map[j][i]=INF;
              }
    
              else
              {
                  sscanf(cost,"%d",&temp);//sscanf表示从字符串中格式化输入，temp为整型的cost 
                  map[i][j]=temp;
                  map[j][i]=temp;
              }       
           } 
       }
       
       cout<<Dijkstra()<<endl;
    } 
    //system("pause");
    return 0;
}