首页 > 代码库 > 网络延时
网络延时
问题描述
给定一个公司的网络,由n台交换机和m台终端电脑组成,交换机与交换机、交换机与电脑之间使用网络连接。交换机按层级设置,编号为1的交换机为根交换机,层级为1。其他的交换机都连接到一台比自己上一层的交换机上,其层级为对应交换机的层级加1。所有的终端电脑都直接连接到交换机上。
当信息在电脑、交换机之间传递时,每一步只能通过自己传递到自己所连接的另一台电脑或交换机。请问,电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。
输入格式
输入的第一行包含两个整数n, m,分别表示交换机的台数和终端电脑的台数。
第二行包含n - 1个整数,分别表示第2、3、……、n台交换机所连接的比自己上一层的交换机的编号。第i台交换机所连接的上一层的交换机编号一定比自己的编号小。
第三行包含m个整数,分别表示第1、2、……、m台终端电脑所连接的交换机的编号。
输出格式
输出一个整数,表示消息传递最多需要的步数。
样例输入
4 2
1 1 3
2 1
样例输出
4
1 #include<iostream> 2 #include<cstdio> //don‘t forget 3 #include<cstring> //don‘t forget 4 #include<algorithm> 5 #include<vector> 6 #include<queue> 7 8 using namespace std; 9 10 #define N 20005 11 12 13 vector<int> switchboard[N]; 14 bool vis[N]; 15 int d[N]; 16 queue<int> q; 17 int n, m; 18 19 int bfs(int s, int &t){ 20 memset(d, 0, sizeof(d)); 21 memset(vis, 0, sizeof(vis)); 22 t = s; 23 int ans = 0; 24 q.push(s); 25 vis[s] = 1; 26 while (!q.empty()){ 27 int u = q.front(); 28 q.pop(); 29 for (int i = 0; i<switchboard[u].size(); i++){ 30 int v = switchboard[u][i]; 31 if (!vis[v]){ 32 vis[v] = 1; 33 d[v] = d[u] + 1; 34 if (d[v]>ans){ 35 ans = d[v]; 36 t = v; 37 } 38 q.push(v); 39 } 40 } 41 } 42 return ans; 43 } 44 45 int main() { 46 int number, i; 47 cin >> n >> m; 48 for (i = 2; i <= n; i++) 49 { 50 cin >> number; 51 switchboard[i].push_back(number); 52 switchboard[number].push_back(i); 53 } 54 for (i = 1; i <= m; i++) 55 { 56 cin >> number; 57 switchboard[i + n].push_back(number); 58 switchboard[number].push_back(i + n); 59 } 60 61 int p, ans = bfs(1, p); 62 ans = max(bfs(p, p), ans); 63 cout << ans << endl; 64 65 return 0; 66 }
网络延时
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。