题意:给定一个n台计算机的网络的连接图,这个图是一棵树的形式。现在要以某一台计算机为路由器,问其它的计算机到路由器的最长的距离的最小值
思路:给定一个树,我们能够求出树的直径。那么直径的两端的距离是最长的,那么路由器的选择肯定是在树的直径上面的某一点,因为要距离最小因此选择中间的点肯定能够满足。那么maxLen为直径的话,ans为(maxLen+1)/2
代码:
#include<vector> #include<queue> #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int MAXN = 100010; struct Node{ int num; int step; }; int n , start , maxLen; bool vis[MAXN]; vector<int>v[MAXN]; queue<Node>q; void init(){ for(int i = 0 ; i < n ; i++) v[i].clear(); int x , y; for(int i = 1 ; i < n ; i++){ scanf("%d%d" , &x , &y); v[x].push_back(y); v[y].push_back(x); } } void bfs(){ maxLen = 0; while(!q.empty()){ Node tmp = q.front(); q.pop(); int x = tmp.num; int size = v[x].size(); bool isOk = false; vis[x] = true; for(int i = 0 ; i < size ; i++){ if(!vis[v[x][i]]){ q.push((Node){v[x][i] , tmp.step+1}); isOk = true; } } if(!isOk && maxLen < tmp.step){ maxLen = tmp.step; start = x; } } } int solve(){ while(!q.empty()) q.pop(); q.push((Node){0,0}); memset(vis , false , sizeof(vis)); bfs(); while(!q.empty()) q.pop(); q.push((Node){start,0}); memset(vis , false , sizeof(vis)); bfs(); return (maxLen+1)/2; } int main(){ int cas; scanf("%d" , &cas); while(cas--){ scanf("%d" , &n); init(); printf("%d\n" , solve()); } return 0; }