POJ1655 Balancing Act

　　题意很容易理解：去掉某个节点，求得到的森林中树最多有几个节点。

　　这道题为动态规划题，我的做法是这样的：开两个数组，dp1[]和dp2[]，dp1[i]记录以i为根的树的总节点数， dp2[i]记录去掉节点i时得到的平衡度（所有子树中最多的节点数），此时计算dp2就是目标，那么，我可以进行两次dfs，dfs1搜索完成后得到dp1，dfs2完成后得到dp2，对于两次搜索，其核心分别是：

dfs1：

　　 dp1[i] += dp1[k]; (k为节点i的子节点）
dp2[i] = max(dp2[i], dp1[k]+1); (此时得到的dp2是单向向下的，因为防止深搜死循环，暂时不考虑其父节点所领导的树）

dfs2:

　　 dp2[i]= max(dp2[i], n - dp1[i]); (这条动规方程由图很容易推出来）

　　 dfs的时候选取任意一个节点为根节点即可，两次dfs的时间复杂度都是O(n)，所以总时间复杂度也是O(n)。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <math.h>
 4 #include <stdlib.h>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 using namespace std;
 9 const int maxn = 20000 + 5;
10 vector<int> vt[maxn];
11 int dp1[maxn];     // 记录当前节点为根的树的节点数
12 int dp2[maxn];     // 当前节点的平衡度（所有子树中最多的节点数）
13 bool h[maxn];
14 int n;
15 int dfs1(int k)
16 {
17     dp1[k] = 1;
18     dp2[k] = 1;
19     h[k] = true;
20     int p = vt[k].size();
21     for(int i = 0; i < p; i++)
22     {
23         if(!h[vt[k][i]])
24         {
25             int tmp = dfs1(vt[k][i]);
26             dp1[k] += tmp;
27             dp2[k] = max(dp2[k], tmp+1);
28         }
29     }
30     return dp1[k];
31 }
32 
33 void dfs2(int k)
34 {
35     h[k] = true;
36     int p = vt[k].size();
37     for(int i = 0; i < p; i++)
38     {
39         if(!h[vt[k][i]])
40         {
41             dp2[vt[k][i]] = max(dp2[vt[k][i]], n - dp1[vt[k][i]]);
42             dfs2(vt[k][i]);
43         }
44         
45     }
46 }
47 
48 void init()
49 {
50     memset(h, false, sizeof h);
51     for(int i = 1; i <= n; i++)
52         vt[i].clear();
53 }
54 
55 int main()
56 {
57     int t, x, y, a1, a2;
58     scanf("%d", &t);
59      while(t--)
60     {
61         scanf("%d", &n);
62         init();
63         for(int i = 0; i < n - 1; i++)
64         {
65             scanf("%d %d", &x, &y);
66             vt[x].push_back(y);
67             vt[y].push_back(x);
68         }
69 
70         dfs1(1);
71         for(int i = 1; i <= n; i++)
72             dp2[i] -= 1;
73 
74         memset(h, false, sizeof h);
75         dfs2(1);
76 
77         a2 = 10000000;
78         for(int i = 1; i <= n; i++)
79         {
80             if(dp2[i] < a2)
81                 a1 = i, a2 = dp2[i];
82         }
83         printf("%d %d\n", a1, a2);
84     }
85     return 0;
86 }