树形dp求树的重心

分类: IT文章 • 2024-10-24 20:50:48

Balancing Act http://poj.org/problem?id=1655

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 #define mt(a,b) memset(a,b,sizeof(a))
 6 using namespace std;
 7 const int M=50010;
 8 vector<int> g[M];
 9 int dp[M],num[M],n;
10 void dfs(int u,int fa){
11     dp[u]=0;
12     num[u]=1;
13     int len=g[u].size();
14     for(int i=0;i<len;i++){
15         int v=g[u][i];
16         if(v!=fa){
17             dfs(v,u);
18             num[u]+=num[v];
19             dp[u]=max(dp[u],num[v]);
20         }
21     }
22     dp[u]=max(dp[u],n-num[u]);
23 }
24 int main(){
25     int t;
26     while(~scanf("%d",&t)){
27         while(t--){
28             scanf("%d",&n);
29             for(int i=1;i<=n;i++) g[i].clear();
30             for(int i=0,u,v;i<n-1;i++){
31                 scanf("%d%d",&u,&v);
32                 g[u].push_back(v);
33                 g[v].push_back(u);
34             }
35             dfs(1,-1);
36             int sma=n;
37             for(int i=1;i<=n;i++){
38                 sma=min(sma,dp[i]);
39             }
40             for(int i=1;i<=n;i++){
41                 if(dp[i]==sma){
42                     printf("%d %d
",i,dp[i]);
43                     break;
44                 }
45             }
46         }
47     }
48     return 0;
49 }

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<vector>
 5 #define mt(a,b) memset(a,b,sizeof(a))
 6 using namespace std;
 7 const int M=50010;
 8 struct G{
 9     struct E{
10         int u,v,next;
11     }e[M<<1];
12     int le,head[M];
13     void init(){
14         le=0;
15         mt(head,-1);
16     }
17     void add(int u,int v){
18         e[le].u=u;
19         e[le].v=v;
20         e[le].next=head[u];
21         head[u]=le++;
22     }
23 }g;
24 int dp[M],num[M],n;
25 void dfs(int u,int fa){
26     dp[u]=0;
27     num[u]=1;
28     for(int i=g.head[u];~i;i=g.e[i].next){
29         int v=g.e[i].v;
30         if(v!=fa){
31             dfs(v,u);
32             num[u]+=num[v];
33             dp[u]=max(dp[u],num[v]);
34         }
35     }
36     dp[u]=max(dp[u],n-num[u]);
37 }
38 int main(){
39     int t;
40     while(~scanf("%d",&t)){
41         while(t--){
42             scanf("%d",&n);
43             g.init();
44             for(int i=0,u,v;i<n-1;i++){
45                 scanf("%d%d",&u,&v);
46                 g.add(u,v);
47                 g.add(v,u);
48             }
49             dfs(1,-1);
50             int sma=n;
51             for(int i=1;i<=n;i++){
52                 sma=min(sma,dp[i]);
53             }
54             for(int i=1;i<=n;i++){
55                 if(dp[i]==sma){
56                     printf("%d %d
",i,dp[i]);
57                     break;
58                 }
59             }
60         }
61     }
62     return 0;
63 }

View Code

Godfather http://poj.org/problem?id=3107

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 const int M=50010;
 7 struct G{
 8     struct E{
 9         int u,v,next;
10     }e[M<<1];
11     int le,head[M];
12     void init(){
13         le=0;
14         mt(head,-1);
15     }
16     void add(int u,int v){
17         e[le].u=u;
18         e[le].v=v;
19         e[le].next=head[u];
20         head[u]=le++;
21     }
22 }g;
23 int dp[M],num[M],n;
24 void dfs(int u,int fa){
25     dp[u]=0;
26     num[u]=1;
27     for(int i=g.head[u];~i;i=g.e[i].next){
28         int v=g.e[i].v;
29         if(v!=fa){
30             dfs(v,u);
31             num[u]+=num[v];
32             dp[u]=max(dp[u],num[v]);
33         }
34     }
35     dp[u]=max(dp[u],n-num[u]);
36 }
37 int main(){
38     while(~scanf("%d",&n)){
39         g.init();
40         for(int i=0,u,v;i<n-1;i++){
41             scanf("%d%d",&u,&v);
42             g.add(u,v);
43             g.add(v,u);
44         }
45         dfs(1,-1);
46         int sma=n;
47         for(int i=1;i<=n;i++){
48             sma=min(sma,dp[i]);
49         }
50         for(int i=1;i<=n;i++){
51             if(dp[i]==sma){
52                 printf("%d ",i);
53             }
54         }
55         puts("");
56     }
57     return 0;
58 }

View Code

end

树形dp求树的重心

相关推荐