Gym - 102222G Factories （树形DP）

75 阅读 0 评论 50 点赞

我是靠谱客的博主标致丝袜，最近开发中收集的这篇文章主要介绍Gym - 102222G Factories （树形DP），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Factories

Byteland has nn cities numbered from 11 to nn, and n−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 kk 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

The input contains several test cases, and the first line is a positive integer TTindicating the number of test cases which is up to 103103.

For each test case, the first line contains two integers n (2≤n≤105)n (2≤n≤105) and k (1≤k≤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−1 lines contains three integers u,v (1≤u,v≤n)u,v (1≤u,v≤n) and w (1≤w≤105)w (1≤w≤105) which describes a road between the city uu and the city vv of length ww.

We guarantee that the number of leaves in the road network is no smaller than kk, and the sum of nn in all test cases is up to 106106.

Output

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

Example

Input

Output

Case #1: 5
Case #2: 18

题目链接：http://codeforces.com/gym/102222/problem/G

题目大意：有n个城市，要建m个工厂，有n-1条路 u v w，一个城市只能建一个工厂，工厂只能建在叶子节点上（即这个城市只能有一条边），问这m个工厂，任意两个工厂间的距离的和的最小值

思路：树形DP，考虑边对答案的贡献，dp[ u ][ j ] 表示以 u 为根节点的子树上建 j 个工厂的最小权值和（子树中边对最终答案的贡献和），状态转移方程： dp[ u ][ j ] = min( dp[ u ][ j ]，dp[ u ][ j - k ] + dp[ v ][ k ] + w*k*(m-k) ) w是u到v的权值， k*（m-k）是这条边在最终答案中计算的次数， w*k*（m-k）就是这条边对最终答案的贡献

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f3f3f
using namespace std;
const int N=100005;
struct node
{
int v,nex;
ll w;
}e[N<<1];
int n,m,tot,first[N],in[N],siz[N];
ll dp[N][105];
void init()
{
tot=0;
memset(first,-1,sizeof(first));
memset(in,0,sizeof(in));
memset(siz,0,sizeof(siz));
}
void adde(int u,int v,ll w)
{
e[tot].v=v,e[tot].w=w;
e[tot].nex=first[u];
first[u]=tot++;
}
void dfs(int u,int fa)
{
if(in[u]==1)
{
siz[u]=1;
dp[u][1]=0;
}
for(int i=first[u];~i;i=e[i].nex)
{
int v=e[i].v;
ll w=e[i].w;
if(v==fa) continue;
dfs(v,u);
siz[u]+=siz[v];
for(int j=min(m,siz[u]);j>=1;j--)
for(int k=1;k<=min(siz[v],j);k++)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]+w*k*(m-k));
}
}
int main()
{
int t,T=1;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d%d",&n,&m);
int x,y;
ll w;
for(int i=1;i<n;i++)
{
scanf("%d%d%lld",&x,&y,&w);
adde(x,y,w);
adde(y,x,w);
in[x]++,in[y]++;
}
int rt=1;
for(int i=1;i<=n;i++)
if(in[i]>1)
{
rt=i;
break;
}
for(int i=1;i<=n;i++)
{
dp[i][0]=0;
for(int j=1;j<=m;j++)
dp[i][j]=inf;
}
dfs(rt,-1);
printf("Case #%d: %lldn",T++,dp[rt][m]);
}
return 0;
}