POJ 3107 dfs 树的重心

树的重心

题意：

给出一棵树，现在让拿去一个节点，问拿去那个节点使得剩下的森林中最大的节点个数最小？

思路：

当拿去一个节点的时候，不知道拿去那个，但是可以通过深度搜索把每一个节点都遍历，对于一个节点u：

当拿去时答案就在它的父亲节点有多少个和儿子节点中最大的那个之中，所以一个深搜即可。

问题是如果建图用vector会超时，可见STL之中虽然便捷但是很慢，选择用邻接表来建立，head[u]表示与u相连的节点下标next表示上一个与u相连的节点下标。输入采用了模拟输入，比起scanf更快。

超时代码：

#include <iostream> #include <cstdio> #include <vector> using namespace std; inline int read() { char k = 0,ls; ls=getchar(); for(;ls<'0'||ls>'9';k = ls,ls = getchar()); int x=0; for(;ls >= '0' && ls <= '9';ls = getchar()) x=x*10+ls-'0'; if(k == '-') x=0-x; return x; } const int maxn = 50005; const int inf = 0x3f3f3f3f; int n,node; int sonNumber[maxn],vis[maxn]; int allans[maxn]; vector<int>G[maxn]; void dfs(int u) { int Max = 0; sonNumber[u] = 0; vis[u] = true; int len = G[u].size(); for(int i = 0;i < len; i++) { int to = G[u][i]; if(vis[to]) continue; dfs(to); sonNumber[u] += sonNumber[to] + 1; Max = max(Max,sonNumber[to] + 1); } Max = max(Max,n - sonNumber[u] - 1); allans[u] = Max; if(node > Max) { node = Max; } } int main(int argc, char const *argv[]) { //freopen("in.txt","r",stdin); n = read(); for(int i = 1;i < n; i++) { int s,e; s = read(),e = read(); G[s].push_back(e); G[e].push_back(s); } node = inf; dfs(1); int flag = true; for(int i = 1;i <= n; i++) { if(node == allans[i]) { if(flag) printf("%d",i),flag = false; else printf(" %d",i); } } printf("\n"); return 0; }

110ms代码

#include <iostream> #include <cstdio> #include <vector> #include <cstring> using namespace std; inline int read() { char k = 0,ls; ls=getchar(); for(;ls<'0'||ls>'9';k = ls,ls = getchar()); int x=0; for(;ls >= '0' && ls <= '9';ls = getchar()) x=x*10+ls-'0'; if(k == '-') x=0-x; return x; } const int maxn = 50005; const int inf = 0x3f3f3f3f; int n,node; int sonNumber[maxn],vis[maxn]; int allans[maxn]; int head[maxn],pos; struct Node { int e; int next; }edge[maxn*2]; void dfs(int u) { int Max = 0; sonNumber[u] = 0; vis[u] = true; for(int i = head[u];i != -1; i = edge[i].next) { int to = edge[i].e; if(!vis[to]) { dfs(to); sonNumber[u] += sonNumber[to] + 1; Max = max(Max,sonNumber[to] + 1); } } Max = max(Max,n - sonNumber[u] - 1); allans[u] = Max; if(node > Max) { node = Max; } } int main(int argc, char const *argv[]) { //freopen("in.txt","r",stdin); n = read(); memset(head,-1,sizeof(head)); pos = 0; for(int i = 1;i < n; i++) { int a,b; a = read(),b = read(); edge[pos].e = b; edge[pos].next = head[a]; head[a] = pos++; edge[pos].e = a; edge[pos].next = head[b]; head[b] = pos++; } node = inf; dfs(1); int flag = true; for(int i = 1;i <= n; i++) { if(node == allans[i]) { if(flag) printf("%d",i),flag = false; else printf(" %d",i); } } printf("\n"); return 0; }