Preparing NOJ

有向树k中值问题

1000ms 65536K

Description:

给定一棵有向树T,树T中每个顶点u都有一个权w(u);树的每条边(u,v)也都有一个非负边长d(u,v)。有向树T的每个顶点u可以看作客户,其服务需求量为w(u)。每条边(u,v)的边长d(u,v)可以看作运输费用。如果在顶点u处未设置服务机构,则将顶点u处的服务需求沿有向树的边(u,v)转移到顶点v处服务机构需付出的服务转移费用为w(u)*d(u,v)。树根处已设置了服务机构,现在要在树T中增设k处服务机构,使得整棵树T 的服务转移费用最小。

对于给定的有向树T,编程计算在树T中增设k处服务机构的最小服务转移费用。

Input:

输入的第1 行有2个正整数nkn表示有向树T的边数;k是要增设的服务机构数。有向树T 的顶点编号为01,…,n。根结点编号为0。接下来的n行中,每行有表示有向树T的一条有向边的3个整数。第i+1行的3个整数wi,vi,di分别表示编号为i的顶点的权为wi,相应的有向边为(i, vi),其边长为di

Output:

输出计算的最小服务转移费用。

Sample Input:

4 2
1 0 1
1 1 10
10 2 5
1 2 3

Sample Output:

4

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1240

Tags

Submitted 4

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet