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

1
2
3
4
5
6
7
8
9
2
4 2
1 2 2
1 3 3
1 4 4
4 3
1 2 2
1 3 3
1 4 4

Output

1
2
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）就是这条边对最终答案的贡献

代码：

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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;
}

最后

以上就是标致丝袜最近收集整理的关于Gym - 102222G Factories （树形DP）的全部内容，更多相关Gym内容请搜索靠谱客的其他文章。