首页 > 代码库 > P1395 会议（求树的重心）
P1395 会议（求树的重心）
P1395 会议
题目描述
有一个村庄居住着n个村民，有n-1条路径使得这n个村民的家联通，每条路径的长度都为1。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。
输入输出格式
输入格式：
第一行。一个数n，表示有n个村民。
接下来n-1行，每行两个数字a和b，表示村民a的家和村民b的家之间存在一条路径。
输出格式：
一行输出两个数字x和y
x表示村长将会在哪个村民家中举办会议
y表示距离之和的最小值
输入输出样例
输入样例#1：
41 2 2 3 3 4
输出样例#1：
2 4
说明
【数据范围】
70%数据n<=1000
100%数据n<=50000
1 #include<cstdio> 2 #include<algorithm> 3 4 using namespace std; 5 const int MAXN=50005,INF=1e9; 6 struct Edge{ 7 int to,nxt; 8 }e[MAXN<<1]; 9 int n,cnt,ans,minn,size=INF;10 int head[MAXN<<1],son[MAXN],dep[MAXN];11 bool vis[MAXN];12 13 void add(int u,int v)14 {15 ++cnt;16 e[cnt].to = v;17 e[cnt].nxt = head[u];18 head[u] = cnt;19 }20 21 void dfs(int cur)22 {23 vis[cur] = true;24 son[cur] = 0;25 int tmp = 0;26 for (int i=head[cur]; i; i=e[i].nxt)27 {28 if (!vis[e[i].to])29 {30 dfs(e[i].to);31 son[cur] += son[e[i].to]+1; //加上自己32 tmp = max(tmp,son[e[i].to]+1) ;33 }34 }35 tmp = max(tmp,n-son[cur]-1);36 if(size>tmp || (tmp==size&&ans>cur))37 {38 ans = cur;39 size = tmp;40 }41 }42 void dfsdep(int x,int p,int d) 43 {44 dep[x] = d;45 for (int i=head[x]; i; i=e[i].nxt)46 if(p!=e[i].to)47 dfsdep(e[i].to,x,d+1);48 }49 int main()50 {51 scanf("%d",&n);52 for (int x,y,i=1; i<n; ++i)53 {54 scanf("%d%d",&x,&y);55 add(x,y);56 add(y,x);57 }58 dfs(1);59 dfsdep(ans,ans,0);60 for (int i=1; i<=n; ++i)61 minn += abs(dep[ans]-dep[i]);62 printf("%d %d",ans,minn);63 return 0;64 }
P1395 会议（求树的重心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。