【Tree】

【题目描述】

给你一堆边,其中有些边为黑色,有些边为白色,每条边有一条边权。

这些边一定能构造成一颗树,请问其中恰好选K条白边的最小生成树的权值和是多少?

【输入格式】

第一行三个整数n m k表示点数,边数,以及K

接下来m行每行四个整数u v w c表示u到c有一条权值为w颜色为c(0为白色1为黑色)的边(双向边)

【输出格式】

一行一个整数,表示恰好选K条边的最小的权值和

【输入样例】

2 2 1
0 1 1 1
0 1 2 0

【输入样例】

2

【数据范围】

记不清了 貌似是2≤n≤100000,1≤m≤200000 1≤K≤m

让我们来想想怎么才能恰好选K条边。

其实,可以对每条白边都加上一个delta然后二分答案看加上这个delta之后的最小生成树有多少条白边,如果少了,那么说明白边边权更小才能有更多的白边加入,否则白边边权更大才能使最小生成树中的白边尽可能少。因为对所有白边都加了delta所以其实最终不影响白边之间的情况,所以这个算法是正确的。

注意恰好选K条的限制,意思就是如果你选了多余K条是不合法的,也就是说二分的时候最多就选K条,多余的白边还是选,但不记录。

二分的时候搞MST验证即可。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*