luogu P1395 会议
2024-09-04 17:14:43
题目描述
有一个村庄居住着n个村民,有n-1条路径使得这n个村民的家联通,每条路径的长度都为1。现在村长希望在某个村民家中召开一场会议,村长希望所有村民到会议地点的距离之和最小,那么村长应该要把会议地点设置在哪个村民的家中,并且这个距离总和最小是多少?若有多个节点都满足条件,则选择节点编号最小的那个点。
输入输出格式
输入格式:
第一行。一个数n,表示有n个村民。
接下来n-1行,每行两个数字a和b,表示村民a的家和村民b的家之间存在一条路径。
输出格式:
一行输出两个数字x和y
x表示村长将会在哪个村民家中举办会议
y表示距离之和的最小值
输入输出样例
输入样例#1:
4
1 2
2 3
3 4
输出样例#1:
2 4
说明
【数据范围】
70%数据n<=1000
100%数据n<=50000
找树的重心,dfs
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = ;
int n;
int num;
int head[];
struct node{
int v,next,w;
}edge[*];
int son[N],siz;bool vis[N];int ans=;
void add_edge(int x,int y)
{
edge[++num].v=y;edge[num].w=;edge[num].next=head[x];head[x]=num;
}
void dfs(int x)
{
vis[x]=;
son[x]=;
int tmp=;
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
{
dfs(v);
son[x]+=son[v]+;
tmp=max(tmp,son[v]+);
}
}
tmp=max(tmp,n-son[x]-);
if(siz>tmp||tmp==siz&&ans>x)
{
ans=x;
siz=tmp;
}
}
int aans;int dep[N];
void dfs2(int x,int fa,int step)
{
dep[x]=step;
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].v;
if(v==fa)continue;
dfs2(v,x,step+);
}
}
int main()
{
scanf("%d",&n);int u,v;
for(int i=;i<=n-;i++)
{
scanf("%d%d",&u,&v);add_edge(u,v);add_edge(v,u);
}
siz=0x7fffffff;
dfs();
dfs2(ans,ans,);
for(int i=;i<=n;i++)
aans+=abs(dep[ans]-dep[i]);
printf("%d %d",ans,aans);
return ; }
最新文章
- HTML 头部标记
- MongoDB集群架构及搭建
- PYTHON 集合set 方法
- Android开发EditText属性
- 集成学习原理:Adaboost
- java 枚举类小结 Enum
- Hibernate实体类注解
- [iOS 多线程 &; 网络 - 1.1] - 多线程NSThread
- byte[] bytes和string转换
- Bash判断文件是否存在
- .NET MVC4 实训记录之六(利用ModelMetadata实现资源的自主访问)
- ios下点击穿透focus获取问题
- 毕业回馈-89C51之GPIO使用(流水灯)
- Win 10 系统下研华采集卡Advantech Navi SDK虚拟demo设备安装方法
- oracle 按表数据新增一行
- Netty源码分析之服务启动
- Spark进阶之路-Standalone模式搭建
- Android 颜色透明度换算
- 在“安装”阶段发生异常。 System.Security.SecurityException: 未找到源,但未能
- netty--NioEventLoop滴干活