BNUOJ 13358 Binary Apple Tree
Binary Apple Tree
64-bit integer IO format: %lld Java class name: (Any)
2 5 \ / 3 4 \ / 1 |
Input
Output
Sample Input
5 2 1 3 1 1 4 10 2 3 20 3 5 20
Sample Output
21
Source
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 struct arc { 18 int to,w; 19 arc(int x = 0,int y = 0):to(x),w(y) {} 20 }; 21 vector<arc>g[110]; 22 int n,m,dp[110][110],cnt[110]; 23 void dfs(int u,int fa) { 24 cnt[u] = 1; 25 for(int i = 0; i < g[u].size(); i++) { 26 if(g[u][i].to == fa) continue; 27 dfs(g[u][i].to,u); 28 cnt[u] += cnt[g[u][i].to]; 29 } 30 for(int i = 0; i < g[u].size(); i++) { 31 if(g[u][i].to == fa) continue; 32 for(int j = cnt[u]; j > 0; j--) { 33 for(int k = 1; k <= cnt[g[u][i].to] && k < j; k++) { 34 dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[g[u][i].to][k]+g[u][i].w); 35 } 36 } 37 } 38 } 39 int main() { 40 int i,u,v,w; 41 while(~scanf("%d %d",&n,&m)) { 42 for(i = 0; i <= n; i++) 43 g[i].clear(); 44 for(i = 1; i < n; i++) { 45 scanf("%d %d %d",&u,&v,&w); 46 g[u].push_back(arc(v,w)); 47 g[v].push_back(arc(u,w)); 48 } 49 memset(dp,0,sizeof(dp)); 50 dfs(1,-1); 51 printf("%d\n",dp[1][m+1]); 52 } 53 return 0; 54 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。