给出一个带权的连通无向图,对于其中的每条边i,在原来边权的基础上,其边权每增加1需要付出的代价为Ai,边权每减少1需要付出的代价为Bi,现在指定该图的一棵生成树,求通过修改边权,使得该生成树成为图的一棵最小生成树,需要付出的最少总代价。
F.A.Qs | Home | ProblemSet | Status | Ranklist | Contest | Login | Register | 捐赠本站 |
---|
【Hint】
样例解释:
最优方案为:(1, 4)边权加2,代价6;(3, 5)边权加3,代价3;(3, 6)边权加4,代价8;(4, 5)边权减2,代价4;总代价21。
数据范围:
1<=N<=300, 1<=M, Wi, Ai, Bi<=1000。