bzoj#P3118. Orz the MST
Orz the MST
题目描述
给出一个带权的连通无向图,对于其中的每条边 ,在原来边权的基础上,其边权每增加1需要付出的代价为 ,边权每减少 需要付出的代价为 ,现在指定该图的一棵生成树,求通过修改边权,使得该生成树成为图的一棵最小生成树,需要付出的最少总代价。
输入格式
第一行两个正整数 ,表示图的点数和边数,点以 编号; 接下来 行,每行六个正整数 ,表示一条边 权为 ,在原边权基础上增加 的边权代价为 ,减少 的边权代价为 , 若为 则表示该边在指定的生成树中,若为 表示不在。数据保证 值为 的边刚好组成原图的一棵生成树。两点之间可能有多条不同的边,但没有连接同一点的边。
输出格式
输出一个正整数,表示所需付出的最少总代价。
6 8
1 2 3 1 4 2
1 4 2 0 3 4
2 3 5 1 2 1
2 4 4 1 3 5
3 5 2 0 1 3
3 6 1 0 2 4
4 5 7 1 3 2
5 6 5 1 5 4
21
样例说明:
最优方案为: 边权加 ,代价 ; 边权加 ,代价 ; 边权加 ,代价 ; 边权减 ,代价 ;总代价 。
数据规模与约定
对于 的数据,,。