http://acm.timus.ru/problem.aspx?space=1&num=1018
树型DP
1 #include <iostream>
2 using namespace std;
3 const int OO=20000000;
4 int n,m;
5 int q[111];
6 int apple[111];
7 int link[111][2];
8 int son[111];
9 int applesum[111];
10 int dp[111][111],st,en;
11 bool v[111];
12 int map[111][111];
13 int sum;
14
15 void bfs(){
16 st=0; en=1;
17 q[1]=1;
18 v[1]=true;
19 while (st<en){
20 ++st;
21 int nx=q[st];
22 for (int i=1;i<=n;++i) if (!v[i]&&map[nx][i]){
23 ++en;
24 q[en]=i;
25 v[i]=true;
26 apple[i]=map[nx][i];
27 if (link[nx][0]){
28 link[nx][1]=i;
29 break;
30 }
31 else link[nx][0]=i;
32 }
33 }
34 }
35
36 int max(int a,int b){
37 return a>b?a:b;
38 }
39
40 void calc(int x){
41 dp[x][son[x]]=max(dp[x][son[x]],applesum[x]);
42 dp[x][1]=apple[x];
43 int l=link[x][0],r=link[x][1];
44 for (int i=0;i<=m;++i)
45 for (int j=0;j<=m;++j){
46 dp[x][i+j+1]=max(dp[x][i+j+1],dp[l][i]+dp[r][j]+apple[x]);
47 }
48 }
49
50 int main(){
51 scanf("%d %d",&n,&m);
52 ++m;
53 for (int i=1;i<n;++i){
54 int a,b,c;
55 scanf("%d %d %d",&a,&b,&c);
56 map[a][b]=map[b][a]=c;
57 sum+=c;
58 }
59 bfs();
60 for (int i=n;i>0;--i){
61 son[q[i]]=son[link[q[i]][0]]+son[link[q[i]][1]]+1;
62 applesum[q[i]]=applesum[link[q[i]][0]]+applesum[link[q[i]][1]]+apple[q[i]];
63 }
64 for (int i=n;i>0;--i) calc(q[i]);
65 cout<<dp[1][m];
66 }
67
posted on 2008-11-04 09:36
Joseph 阅读(171)
评论(0) 编辑 收藏 引用