/*依赖背包的通常做法就是对于每个结点，先处理处其所有子节点的dp，然后对于当前结点进行分组背包dp即可
还是依赖背包问题，dp[i][j]表示结点i的子树用了j个机器人的搜索代价
边界条件，如果某个结点的子树用了0个机器人，那么搜索这个棵子树的代价是边权和*2
将每个结点子树中的机器人看做物品体积，搜索代价看做价值，求最小价值
*/
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int to,nxt,w;}edge[
10005<<
1];
int head[
10005],tot,dp[
10005][
15],n,s,k;
void init(){memset(head,-
1,
sizeof head);tot=
0;}
void addedge(
int u,
int v,
int w){
edge[tot].to=v;edge[tot].nxt=head[u];edge[tot].w=w;head[u]=tot++
;
}
void dfs(
int u,
int pre){
for(
int i=head[u];i!=-
1;i=
edge[i].nxt){
int v=
edge[i].to;
if(v!=
pre)dfs(v,u);
}
for(
int i=head[u];i!=-
1;i=edge[i].nxt){
//分组背包
int v=
edge[i].to;
if(v==pre)
continue;
for(
int j=
10;j>=
0;j--
){
dp[u][j]=dp[u][j]+dp[v][
0]+
2*edge[i].w;
//赋予边界值
for(
int l=
1;l<=j;l++
)
dp[u][j]=min(dp[u][j],dp[u][j-l]+dp[v][l]+l*
edge[i].w);
}
}
}
int main(){
while(scanf(
"%d%d%d",&n,&s,&k)==
3){
init();
int u,v,w;
for(
int i=
1;i<n;i++
){
scanf("%d%d%d",&u,&v,&
w);
addedge(u,v,w);
addedge(v,u,w);
}
memset(dp,0,
sizeof dp);
dfs(s,-
1);
printf("%d\n",dp[s][k]);
}
return 0;
}
转载于:https://www.cnblogs.com/zsben991126/p/10325237.html
