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的服务转
Platform: |
Size: 1362 |
Author: wild_lily |
Hits: