首页 > 代码库 > Zoj 3201 Tree of Tree
Zoj 3201 Tree of Tree
树树
时间限制: 1秒 内存限制: 32768 KB
你给一个树的每个节点的权重,你需要找到这棵树的指定大小的最大子树。
树定义
树是其中不包含任何周期的连通图。
输入
有在输入多个测试用例。
每种情况下的第一行是两个整数N(1 <= N <= 100),K(1 <= K <= N),其中N是该树的节点的数量,K是子树的大小,其次通过与N的非负整数,其中第k个整数表示第k个节点的权重的行。接下来的N - 1行描述了树,每行有两个整数这意味着在这两个节点之间的边缘。以上所有的指标都是零基础,这是保证树的描述是正确的。
产量
一行与对于每种情况,这是最大的子树的总权重的单个整数。
样例输入
3 1
10 20 30
0 1
0 2
3 2
10 20 30
0 1
0 2
样例输出
30
40
树型DP+背包问题!
f[i][j]表示以i为根结点有j个结点子树的最大权值。
以下代码仅供参考!
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; #define MAX 105 vector<int> adj[MAX]; int f[MAX][MAX],tot[MAX],weight[MAX]; int ans,K; int max(int a,int b) { return a>b?a:b; } int DFS(int u,int father) { tot[u]=1; int i,j,k,v; for(i=0;i<adj[u].size();i++) { v=adj[u][i]; if(v==father) // 如果又回到了父节点的情况 continue; tot[u]+=DFS(v,u); } f[u][1]=weight[u]; for(i=0;i<adj[u].size();i++) { v=adj[u][i]; if(v==father) continue; for(j=tot[u];j>=1;j--) { for(k=0;k<j&&k<=tot[v];k++) { f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]); } } } if(tot[u]>=K) ans=max(ans,f[u][K]); return tot[u]; } int main() { int N,i,u,v; while(~scanf("%d%d",&N,&K)) { for(i=0;i<N;i++) { scanf("%d",&weight[i]); adj[i].clear(); } for(i=1;i<N;i++) { scanf("%d%d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } memset(f,0,sizeof(f)); ans=0; DFS(1,-1); printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。