poj 3107 Godfather 求树的重心【树形dp】

poj 3107 Godfather

poj 1655差不多,那道会了这个也就差不多了。

题意:从小到大输出树的重心。

题会卡stl,要用邻接表存树。。。。。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = ;
const int INF = << ;
int head[maxn];
int son[maxn], ans[maxn];
bool vis[maxn];
int n, siz, cnt, tot;
struct Edge
{
int to, next;
};
Edge edge[maxn * ]; void Init()
{
memset(vis, , sizeof(vis));
memset(head, -, sizeof(head));
siz = INF;
cnt = tot = ;
} void add(int u, int v)
{
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
} void dfs(int u)
{
vis[u] = ;
son[u] = ;
int tmp = ;
for (int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if (!vis[v]) {
dfs(v);
son[u] += son[v];
tmp = max(tmp, son[v]);
}
}
tmp = max(tmp, n - son[u]);
if (tmp == siz) {
ans[tot++] = u;
}
else if (tmp<siz) {
tot = ;
ans[tot++] = u;
siz = tmp;
}
} int main()
{
while (scanf("%d", &n) == )
{
Init();
for (int i = ; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
dfs();
sort(ans, ans + tot);
for (int i = ; i<tot; i++) {
printf("%d ", ans[i]);
}
printf("\n");
}
return ;
}
上一篇:POJ 1655 Balancing Act&&POJ 3107 Godfather(树的重心)


下一篇:研究Mysql优化得出一些建设性的方案