点击打开SPOJ 9126
题意:给定一个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;
}
分享到:
相关推荐
杨弋SPOJ做题表格
spoj reverse 的solution
个人这两天做的SPOJ上的题目。。 主要都是前面的几道,不是很多 希望能收到资源分。。
Online Judge Problem solution VN.SPOJ
SPOJ题库( http://www.spoj.pl)的离线题库。 包括索引+内容。PDF格式。 主要是Classical的problemset。
Some solution of problems in SPOJ, all of them use DP technique to attack the problems.
Some Solution of Problem in SPOJ (Sphere Online Judge) solved in various algorithm.
hdu 1914稳定婚姻 sgu176 有源汇的上下界 求最小满足的流 poj 2230 递归求欧拉回路 poj 2985 bst模板 poj2723 2-sat验证,二分答案 poj2455 dinic (ek会超时) hdu1689 求最小奇数环 poj2391 isap最快,dinic不减枝...
SPOJ-Solutions:SPOJ算法问题的解决方案
My solution for some spoj problems
SPOJ( )上选定问题的解决方案
cp:一些SPOJ问题的解决方案
SPOJ-备份工具 介绍 在 Sphere Online Judge ( ) 中,您可以尝试所给的具有挑战性的问题。 它还使您能够查看和下载您自己的解决方案。 工具 SPOJ_BACKUP 备份所有已接受的提交并将它们保存在脚本所在的计算机位置。...
联系 Python中SPOJ问题的解决方案。
分机检查spoj用户的排名。 此扩展名有2个选项: - 在选择的比赛中显示用户排名 - 在选择比赛中最多可比较5个用户第一个在后台运行,并在每隔几分钟内更新,您可以设置自己(并默认为15分钟)。当您单击分机的徽标时...
spoj MSTS kruskal +生成树
检查SPOJ用户等级的扩展名。 这个扩展有两个选项: - 在选择比赛中显示用户等级 - 比较最多5个用户选择比赛 第一个在后台运行,每隔几分钟更新一次,您可以自己设置(默认为15分钟)。 第二个是当你点击分机的标志...
gcd(a,b)= d (d为素数,1,1)
SPOJ上的SUBLEX,后缀自动机实现,可以作为后缀自动机的模板,包含计数排序和dfs两种更新方式实现。
SPOJ解决方案 我已解决的SPOJ问题的解决方案。 仅当您自己尝试过该问题并且无法提出任何解决方案,也可以随意报告任何错误并为该存储库提供解决方案时,才请参考这些解决方案。 我的个人资料链接 会费 分叉仓库并为...