POJ3107--Godfather(树的重心)
2024-10-19 08:59:02
vector建图被卡了。。改为链式前向星500ms过的。。差了四倍多?。。。
表示不太会用链表建图啊。。自己试着写的,没看模板。。嗯。。果然错了。。落了一句话orz
树的重心就是找到一个树中一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后,生成的多棵树尽可能平衡。
根据定义很容易求得。
/***********************************************
Problem: 3107 User: G_lory
Memory: 4440K Time: 500MS
Language: C++ Result: Accepted
***********************************************/ #include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
typedef long long ll; const int N = 500005; struct Edge {
int to, next;
} edge[N];
int head[N]; int cnt;
int sz[N];
int maxn[N]; int n; void add_edge(int u, int v) // 双向边
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
cnt++; edge[cnt].to = u;
edge[cnt].next = head[v];
head[v] = cnt;
cnt++;
} int ans;
void dfs(int u, int pre)
{
sz[u] = 0;
int temp = 0;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (v == pre) continue;
dfs(v, u);
sz[u] += sz[v] + 1;
temp = max(temp, sz[v] + 1);
}
temp = max(n - sz[u] - 1, temp);
maxn[u] = temp;
ans = min(temp, ans);
} int main()
{
while (~scanf("%d", &n))
{
int a, b;
memset(head, -1, sizeof head);
cnt = 1;
for (int i = 1; i < n; ++i)
{
scanf("%d%d", &a, &b);
add_edge(a, b);
}
ans = n;
dfs(1, -1);
int ok = 1;
for (int i = 1; i <= n; ++i)
{
if (maxn[i] == ans)
{
if (ok) ok = 0;
else printf(" ");
printf("%d", i);
}
}
printf("\n");
}
return 0;
}
最新文章
- WebAPI接口返回ArrayList包含Dictionary对象正确解析
- Android编码规范02
- MVC4下配置log4net 五部曲
- Null Object模式
- &ldquo;耐撕&rdquo;团队 2016.3.25 站立会议
- springboot+maven快速构建项目
- 一行代码解决各种IE兼容问题,IE6,IE7,IE8,IE9,IE10(转)
- 注解在android中的使用
- JVM常见垃圾回收算法
- Java 面试知识点解析(五)——网络协议篇
- KVM 热迁移
- JS(JavaScript)的进一步了解6(更新中&#183;&#183;&#183;)
- Docker环境下的Mysql8 实现主从数据库数据同步方案
- zabbix4.0离线快速编译安装(编译安装方法)
- ui-router 1.0 002 未登录跳转到login
- Java Web项目中连接Access数据库的配置方法
- iOS RSA非对称加密测试流程
- js模拟点击打开超链接
- iOS8 CIGlassDistortion滤镜的使用
- gRPC初探——概念介绍以及如何构建一个简单的gRPC服务