首页 > 代码库 > poj 2378 Tree Cutting (树形dp)
poj 2378 Tree Cutting (树形dp)
<a target=_blank href=http://www.mamicode.com/"http://http://poj.org/problem?id=2378">看题目请戳我>#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; #define maxx 10050 int num[maxx];//记录孩子的个数 int dp[maxx];//记录把这个节点删除之后剩下的最大的连通度 int sum; vector <int>root[maxx]; bool vis[maxx]; int dfs(int x)//返回这个数的孩子有几个 { int n=root[x].size(); vis[x]=1; num[x]=1; for(int i=0;i<n;i++) { if(!vis[root[x][i]]) num[x]+=dfs(root[x][i]); } return num[x]; } void woo(int m) { int k; int n=root[m].size(); vis[m]=1; for(int i=0;i<n;i++) { k=root[m][i]; if(vis[k])//如果他已经被遍历过了,判断他的孩子多还是先辈多 { dp[m]=max(dp[m],sum-num[m]); } else//把它孩子的个数赋予它 { dp[m]=max(dp[m],num[k]); woo(k); } } } int main() { while(scanf("%d",&sum)!=EOF) { for(int i=1;i<=sum;i++) root[i].clear(); int a,b; int c=sum; memset(dp,0,sizeof(dp)); for(int i=1;i<sum;i++) { scanf("%d%d",&a,&b); root[a].push_back(b); root[b].push_back(a); } memset(vis,0,sizeof(vis)); dfs(1); memset(vis,0,sizeof(vis)); woo(1); int flag=0; for(int i=1;i<=c;i++) { if(dp[i]<=c/2) { flag=1; printf("%d\n",i); } } if(!flag) puts("NONE"); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。