OI题库

[WC2012] 最小生成树

【问题描述】

给定无向带权连通图 G，我们希望通过修改边的权值，使它的最小生成树唯一。已知减小、增加一条边的权值的单位代价分别为 a 和 b，且修改后的权值必须为非负整数。

例如，对某个图 G，如果将一条边的权值减 3、另一条边的权值加 2 之后，它的最小生成树唯一，则此时的代价之和是 3a+2b。试计算代价之和的最小值。

【输入格式】

输入文件 mst.in 的第一行包含数据编号，对于第 i 个数据，第一行将包含字符串 “mst i”。

第二行包含 4 个正整数 n, m, a, b，分别表示图 G 顶点的个数、边的条数，以及对一条边的权值减 1、加 1 的代价。

接下来 m 行，每行 3 个正整数 x, y, w，表示顶点 x 和顶点 y 之间连有一条初始权值为 w 的边。顶点由 1 至 n 编号。

【输出格式】

输出文件 mst.out 仅包含一行，包含一个非负整数，即要求的最小值。如果无需修改，即图本身的最小生成树就是唯一的，则输出 0。

【样例输入】

mst

45

12

13

23

24

34

0

23

1

1

1

2

2

【样例输出】

5

【样例说明】

将边(2, 4)的权值减 1，边(2, 3)的权值加 1 之后，图 G 的最小生成树唯一，

且此时的代价之和取到最小值。