Tree Cutting POJ - 2378 （树形DP）

佚名 6年前 (2019-04-25) 随笔 830人围观抢沙发百度已收录

题目链接：POJ - 2378

题目大意：给你n个点，然后问你这n个点中，去除哪些点能够使得剩下的图中最大的连通块中点的个数不超过n/2.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

具体思路：第一遍dfs记录每一个点代表的子树大小，第二遍dfs记录每一个点去除的情况下，所剩余的图中最大的联通块中点的个数。

dp[i][0]代表当前i点所代表的子树大小-1

dp[i][1]代表当前i点去除的情况下，所剩余的图中最大的连通块中点的个数。

AC代码：

 1 #include<iostream>  2 #include<stdio.h>  3 #include<cmath>  4 #include<algorithm>  5 #include<string>  6 #include<cstring>  7 #include<vector>  8 using namespace std;  9 # define ll long long 10 const int maxn = 2e5+100; 11 # define inf 0x3f3f3f3f 12 int dp[maxn][2]; 13 int vis[maxn]; 14 vector<int>Edge[maxn]; 15 int n; 16 void init(){ 17 for(int i=0;i<=n;i++){vis[i]=0;} 18 } 19 void dfs1(int u){ 20 vis[u]=1; 21 for(int i=0;i<Edge[u].size();i++){ 22 int to=Edge[u][i]; 23 if(vis[to])continue; 24 dfs1(to); 25 dp[u][0]+=dp[to][0]; 26 } 27 } 28 void dfs2(int u){ 29 vis[u]=1; 30 dp[u][1]=n-dp[u][0]; 31 for(int i=0;i<Edge[u].size();i++){ 32 int to=Edge[u][i]; 33 if(vis[to])continue; 34 dfs2(to); 35 dp[u][1]=max(dp[u][1],dp[to][0]); 36 } 37 } 38 int main() 39 { 40 int st,ed; 41 scanf("%d",&n); 42 for(int i=1;i<=n;i++){dp[i][0]=1;} 43 for(int i=1; i<n; i++) 44  { 45 scanf("%d %d",&st,&ed); 46  Edge[st].push_back(ed); 47  Edge[ed].push_back(st); 48  } 49  init(); 50 dfs1(1); 51  init(); 52 dfs2(1); 53 int flag=1; 54 for(int i=1; i<=n; i++) 55  { 56 if(dp[i][1]*2<=n) 57  { 58 flag=0; 59 printf("%d\n",i); 60  } 61  } 62 if(flag) 63 printf("NONE\n"); 64 return 0; 65 }