HDU_5148

描述

一棵树中挑选相连的k个点出来，求这k个点两两距离之和。

思路

dp[i][j]，表示以i为跟的子树选择j个节点对应的距离对整体的贡献，就是一个树形背包。
dp[u][j] = min { dp[u][j-t] + dp[v][t] + cost(t (k-t) w * 2) } cost是连接u和v的边对整体的贡献。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define ll long long
#define inf 1e18
ll n,K,t;
ll dp[2005][55];
struct mymp{
    int v,len;
};
vector <mymp> st[2005];
void init(){
    for(int i=0 ; i<2005 ;i++)
        for(int j=0 ;j < 55 ; j++)
            dp[i][j]=inf;
    for(int i=0 ; i<2005 ; i++)
        dp[i][0]=dp[i][1]=0;
}
void dfs(int now,int pre){
    vector<mymp>::iterator iter;
    for(iter=st[now].begin() ;  iter<st[now].end() ;iter++){
        if(iter->v==pre)continue;
        int v = iter->v;
        int lenth = iter->len;
        dfs(v,now);
        for(int j = K ; j>= 0; j--){
            for(int l =1 ; l<= j ; l++){
                dp[now][j] = min(dp[now][j], dp[now][j-l] + dp[v][l] + (K-l)*l*2*lenth);
            }
        }
    } 
}
int main(){
    for(cin>>t ; t-- ;){
        ll tmpa,tmpb,tmpc;
        scanf("%I64d%I64d",&n,&K);
        for(int i=1 ;i<=2004 ; i++)st[i].clear();
        init();
        for(int i=1 ; i<= n-1 ;i++){
            scanf("%I64d%I64d%I64d",&tmpa,&tmpb,&tmpc);
            mymp tt;tt.v=tmpb,tt.len=tmpc;
            st[tmpa].push_back(tt);
            tt.v=tmpa;
            st[tmpb].push_back(tt);
        }
        dfs(1,-1);
        printf("%I64d\n",dp[1][K]);
    }
    return 0;
}