随笔 - 32  文章 - 2  trackbacks - 0
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8413
  • 排名 - 1249

最新评论

阅读排行榜

评论排行榜

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 阅读(162) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理