(树形DP) city

Cities

Accepts: 30

Submissions: 125

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

问题描述

很久很久以前，有一个叫做杰哥的骑士. 他生活在一个小王国里. 这个王国由n座城市组成，这n座城市通过n-1条道路相连(意味着这个王国是一棵树结构). 由于杰哥打倒了大魔王，并且从魔王手中救出了公主，国王决定奖励他. 国王决定把公主嫁给杰哥，并且送出恰好K座城市，作为公主的嫁妆.
那么问题来了. 杰哥在和大魔王对♂战的时候，膝盖中了一剑，因此杰哥希望他的K座城市离得越近越好. 这就是说，杰哥希望他的K座城市的期望距离越小越好.
期望距离是这样定义的：首先，从杰哥的K座城市中随机选出一个点u，然后，再从杰哥的K座城市中随机选出一个点v，期望距离就是所有这样u和v的距离的平均值.(注意u可以等于v,此时u和v的距离为0).
请你决定这K座城市，使得杰哥尽量高兴.
你只需要输出最小的期望距离.

输入说明

第一行是一个整数T，表示测试数据的数量.
对于每组测试数据，第一行包含两个整数n和K，表示城市的数量，以及作为奖励的城市数量. 接下来有n-1行，每行三个整数a,b,c，表示有一条长度为c的道路连接城市a和城市b.

数据范围
1 <= T <= 100
1 <= K <= min(50,n)
1 <= n <= 2000
1 <= a,b <= n
0 <= c <= 100000

输出说明

对于每组数据，输出一行包含一个整数，表示最小的期望距离乘以

输入样例

1
2 2
1 2 1

输出样例

2


dp[i][j]表示 以i为根选j个点的子树的最小值
注意初始化 dp[i][0]=dp[i][1]=0;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
#define LL long long
const long long INF=20000*100000000LL;
vector<int> e[2010],w[2010];
int n,k;
LL dp[2010][100],temp[100];
void dfs(int u,int fa)
{
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i];
        if(v==fa)
            continue;
        dfs(v,u);
        for(int j=0;j<=k;j++)
            temp[j]=dp[u][j];
        for(int j=0;j<=k;j++)
        {
            for(int t=0;t<=j;t++)
                temp[j]=min(temp[j],dp[u][j-t]+dp[v][t]+t*(k-t)*w[u][i]*2);
        }
        for(int j=0;j<=k;j++)
            dp[u][j]=temp[j];
    }
}
int main()
{
    int tt,x,y,z;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            e[i].clear();
            w[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            e[x].push_back(y);
            e[y].push_back(x);
            w[x].push_back(z);
            w[y].push_back(z);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=k;j++)
            {
                if(j<=1)
                    dp[i][j]=0;
                else
                    dp[i][j]=INF;
            }
        }
        dfs(1,-1);
        printf("%I64d
",dp[1][k]);
    }
    return 0;
}