本文从WordPress迁移而来, 查看全部WordPress迁移文章
最小树形图
题意:给出3个值X,Y,Z,有n个点,每个点有一个3维坐标,再给出一个点的水可以流向哪些点。水可以从一个点流向另一个点,单向的;也可以在这个点内挖井也不需要通过其它点流过来。要使到每个点都有水,求花费最少。花费的计算方法如下:
两点间流通:u->v,花费为 cost = 两点间曼哈顿距离 Y,如果点v的垂直高度高于u还需要加上花费Z
挖井:该点的垂直高度 X
步骤:
- 有两种方式可以使一个点有水,那么每个点只要选一种方式即可,不需要两种方式都有(这个最优性很明显)
- 除了流通还存在挖井,这个很容易解决,设置一个虚拟顶点0,0指向所有点,边权就是每个点挖井的费用;然后原图上有的边添加进去,就建好图了
- 以0为根,求一次最小树形图即可,直接上模板,模板来自小HH,不过时间很悲剧
1 |
|