POJ 1655 Balancing Act 树形DP入门题

发布时间:2016-12-11 22:08:50 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 1655 Balancing Act 树形DP入门题",主要涉及到POJ 1655 Balancing Act 树形DP入门题方面的内容,对于POJ 1655 Balancing Act 树形DP入门题感兴趣的同学可以参考一下。

View Code #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn = 20003; struct node { int v, next, w; }edge[maxn<<1]; int tot; int head[maxn]; int n; void init() { tot = 0; memset(head, -1, sizeof(int) * (n+1)); } void add(int x, int y) { edge[tot].v = y; edge[tot].next = head[x]; head[x] = tot++; } int maxz(int a, int b) { return a > b ? a : b; } int minz(int a, int b) { return a < b ? a : b; } int ans, kk; int num[maxn]; void dfs(int u, int p) { int i, tmp = 0; num[u] = 0; for(i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(v == p) continue; dfs(v, u); tmp = maxz(tmp, num[v] + 1); num[u] += num[v] + 1; } tmp = maxz(tmp, n - num[u] - 1); if(ans > tmp) { ans = tmp; kk = u; } } int main() { int i, j, cas; int x, y; scanf("%d", &cas); while(cas--) { scanf("%d", &n); init(); for(i = 1; i < n; i++) { scanf("%d%d", &x, &y); add(x, y); add(y, x); } ans = 1<<29; dfs(1, -1); printf("%d %d\n", kk, ans); } return 0; } /* 8 7 2 6 1 2 1 4 4 5 3 7 3 1 */

上一篇:HDU 3586 Information Disturbing 树形DP
下一篇:VC|MFC内存不能为"read",内存不能为 "written" 分析

相关文章

相关评论