【省选模拟赛】小奇挖矿 3

2015年12月17日1,9410

原题:【泉七培训-刘定峰】物流

【题目背景】

小奇在喵星系使用了无限非概率驱动的采矿机,以至于在所有星球上都采出了一些矿石,现在它准备建一些矿石仓库并把矿石运到各个仓库里。

【问题描述】

喵星系有n个星球,标号为1到n,星球以及星球间的航线形成一棵树。

所有星球间的双向航线的长度都为1。小奇要在若干个星球建矿石仓库,设立每个仓库的费用为K。对于未设立矿石仓库的星球,设其到一个仓库的距离为i,则将矿石运回的费用为Di。

请你帮它决策最小化费用。

【输入格式】

第一行2个整数n,K。

第二行n-1个整数,D1,D2,…Dn-1,保证Di<=Di+1。

接下来n-1行,每行2个整数x,y,表示星球x和星球y存在双向航线。

【输出格式】

输出一行一个整数,表示最小费用。

【样例输入】

8 10

2 5 9 11 15 19 20

1 4

1 3

1 7

4 6

2 8

2 3

3 5

【样例输出】

38

【样例解释】

在1,2号星球建立仓库。

【数据范围】

对于30%的数据 n<=15

另外另外20%的数据,每个星球至多与另外两个星球存在双向航线。

对于100%的数据 n<=200,0<=K,Di<=100000

题解

30%的数据n<=15

2^15搜索所有点设立/不设立仓库,每个点bfs得到最近点,计算费用

20%的数据是一条链

不用关心图的连边情况,fi = min{fj + w(j+1 ,i)}

在j+1到i中枚举一个点设立仓库,w(j+1 ,i)为该区间最小费用。复杂度n^3

对于100%的数据

设计状态f(u,Cu)表示距离u的最近仓库为Cu(未建)时,u子树所有点的费用和。

转移时只要枚举结点u的所有儿子,假设当前处理的是儿子v,如果距离v的最近仓库也是Cu,那么直接用f(v,Cu);否则意味着子树v的内部有一个仓库Cv离v最近,那么枚举Cv,转移时再加上设立仓库Cv的费用

取f(1,C1)的最小值+K即为答案。

50分

100分