计蒜客 2018 ICPC宁夏 Factories （树形dp）

Factories

Description

Byteland has nnn cities numbered from 111 to nnn, and n−1n-1n−1 bi-directional roads connecting them.For each pair of cities, the residents can arrive one from another one through these roads (which also means the road network in Byteland is a tree).

Ghaliyah, the queen of the land, has decided to construct kkk new factories.To avoid contamination, she requires that a factory can locate at a city with only one road (which also means this city is a leaf in the road network).Besides, a city can only have one factory.

You, as the royal designer, are appointed to arrange the construction and meanwhile, minimize the sum of distances between every two factories.

Input Format

The input contains several test cases, and the first line is a positive integer TTT indicating the number of test cases which is up to 10310^3103.

For each test case, the first line contains two integers n (2≤n≤105)n~(2\le n \le 10^5)n (2≤n≤105) and k (1≤k≤100)k~(1 \le k \le 100)k (1≤k≤100) indicating the number of cities in Byteland and the number of new factories which are asked to construct.

Each of the following n−1n-1n−1 lines contains three integers u,v (1≤u,v≤n)u, v~(1\le u,v\le n)u,v (1≤u,v≤n) and w (1≤w≤105)w~(1 \le w \le 10^5)w (1≤w≤105) which describes a road between the city uuu and the city vvv of length www.

We guarantee that the number of leaves in the road network is no smaller than kkk, and the sum of nnn in all test cases is up to 10610^6106.

Output Format

For each test case, output a line containing ​​Case #x: y​​, where xxx is the test case number starting from 111, and yyy is the minimum sum of distances between every two factories.

样例输入

2
4 2
1 2 2
1 3 3
1 4 4
4 3
1 2 2
1 3 3
1 4 4

样例输出

Case #1: 5
Case #2: 18

题目来源

​​The 2018 ACM-ICPC Chinese Collegiate Programming Contest​​

大致题意：给你一棵N个节点的树，然后你要在这个树种选择K个叶子节点建立工厂，使得任意两点之间的距离和要最小。

典型的树形dp的题目。我们设dp[x][i]表示在x节点所包的子树内已经选择了i个叶子的最小距离和，那么有状态转移方程dp[x][i]=min(dp[x][i],dp[x][i-j]+dp[son][j]+w*j*(k-j))，其中son表示x的儿子。注意到，dp[x][i]的转移与dp[x][i-j]相关，因此如果正着循环，可能会出现一个叶子节点多次更新一个父亲的情况。所以常规的操作是编程倒着枚举j，但是实际情况下，倒着枚举破坏了cache的空间连续性，访问命中率变低，所以回tle。为了避免这个问题，可用常用套路，即利用一个辅助数组存储当前结果，到所有的转移都判断完毕后再重新复制给dp数组本身。另外，本题数组比较大，不建议使用memset来进行初始化，应该用for手工初始化以节省时间。具体见代码：

#include<bits/stdc++.h>
#define LL long long
#define N 100010

using namespace std;

int sz[N],n,k; LL dp[N][110],tmp[110];
struct Edge{int y,w;};
vector<Edge> g[N];

void dfs(int x,int fa)
{
    if (g[x].size()==1)
    {
        dp[x][1]=dp[x][0]=0;
        sz[x]=1; return;
    }
    sz[x]=0; int t=g[x].size();
    for(int i=1;i<=k;i++) dp[x][i]=2e18;
    for(int i=0;i<t;i++)
    {
        if (g[x][i].y==fa) continue;
        int y=g[x][i].y,w=g[x][i].w;
        dfs(y,x); sz[x]=min(sz[x]+sz[y],k);
        for(int j=0;j<=sz[x];j++) tmp[j]=2e18;
        for(int j=0;j<=sz[x];j++)
            for(int p=0;p<=j&&p<=sz[y];p++)
                tmp[j]=min(tmp[j],dp[x][j-p]+dp[y][p]+w*p*(k-p));
        for(int j=0;j<=sz[x];j++) dp[x][j]=tmp[j];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); int T=0,T_T;
    cin>>T_T;
    while(T_T--)
    {
        cin>>n>>k;
        for(int i=1;i<n;i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            g[u].emplace_back(Edge{v,w});
            g[v].emplace_back(Edge{u,w});
        }
        cout<<"Case #"<<++T<<": ";
        if (n==2)
        {
            if (k==2) cout<<g[1][0].w<<endl;
                 else cout<<0<<endl;
        } else
        {
            int rt=0;
            for(int i=1;i<=n;i++)
            if (g[i].size()>1) {rt=i;break;}
            dfs(rt,0); cout<<dp[rt][k]<<endl;
        }
        for(int i=1;i<=n;i++) g[i].clear();
    }
    return 0;
}