0%

题目链接(UOJ)

题意

一个$n$个结点的无向图,有$m$条老边已经存在,给定起点、终点、权值,保证权值互不相同且此时图已经联通。还有$k$条新边是G老板的,给定起点、终点,权值由G老板指定。

在G老板指定完权值后,在图的最小生成树上,结点$i$上有$p_i$个人要从结点$i$去结点$1$(只能走最小生成树上的边)。每个人如果路过新边就要给G老板交权值那么多钱。求G老板最多赚多少。

$n \le 10^5,m \le 3\times 10^5, k \le 20$,时间限制:$3\operatorname{s} $

阅读全文 »