首页 > 代码库 > poj 1947(树形dp)

poj 1947(树形dp)

2024-07-02 15:33:25   238人阅读

题意：一棵树上问你最少切掉几条边使得能分割出一个结点数正好为k的子树。

思路：dp[i][j]表示以i为根切掉j个结点最少要几条边。

dp[v][j] = min(dp[v][j], dp[v][j-k] + dp[x][k]);

代码如下：

 1                         dp[v][j] = min(dp[v][j], dp[v][j-k] + dp[x][k]);
 2                     }
 3                 }
 4             }
 5         }
 6     }
 7     return vex[v];
 8 }
 9 
10 int main()
11 {
12 //    freopen("in.txt","r",stdin);
13     //freopen("out.txt","w",stdout);
14 
15     int a, b;
16     while(cin >> n >> m){
17         init();
18         for(int i=0; i<n-1; i++){
19             cin >> a >> b;
20             a--,b--;
21             Map[a].PB(b);
22             ind[b] ++;
23         }
24         int rt;
25         for(int i=0; i<n; i++){
26             if(!ind[i]) rt = i;
27         }
28         dfs(rt, -1);
29         int ans = INF;
30         for(int i=0; i<n; i++){
31             if(i!=rt)ans = min(ans, dp[i][vex[i]-m]+1);
32             else ans = min(ans, dp[i][vex[i]-m]);
33         }
34         cout << ans << endl;
35     }
36     return 0;
37 }
View Code

 


联系
我们