题目描述
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。
输入格式
第一行V,E,need分别表示点数，边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。
输出格式
一行表示所求生成树的边权和。
V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。
样例
样例输入
2 2 1
0 1 1 1
0 1 2 0样例输出
2数据范围与提示
原数据出错，现已更新 by liutian,但未重测---2016.6.24
题解：
我们要求一个最小生成树，树中必须恰好包含need条边
在常用的kruskal算法中，一旦边权确定，黑白边就是等价的，但我们要找恰好need条边，所以要让白边尽可能的“特殊”。
想让白边“特殊”，只能给白边改权值。
设用当前的权值求出的最小生成树所含有的白边>need，我们要减少白边数量，就要给每个白边加权值；小于need，要增加白边数量，给白边减权值（加上一个负权）。
那真正的权值怎么求？
我们在kruskal中记录白边个数，白边个数>=need时更新权值：ans=ans-mid×need
一定是白边个数>=need时更新权值，博主在这里卡了半天。
具体原因博主也是看的大佬的题解，现给出解释：
如果在你的二分过程中如果给白边加上mid,你得到的白边数比need大。
给白边加上mid+1,你得到的白边比need小。
这种情况看似没法处理。
但是考虑一下kruskal的加边顺序
可以发现如果出现这种情况，一定是有很多相等的白边和黑边。
因为你排序的时候如果有两条相同权值的黑边和白边，肯定是要把白边排在前面
因为数据保证合法，所以我们可以把一些白边替换成黑边。
所以我们要在白边数>=need的时候更新答案。
那么这个增加的权值如何确定？
二分答案
二分枚举要加上的权值，然后给每个白边加上权值，跑kruskal，出的最小生成树所含有的白边>need，l=mid+1，小于need，r=mid-1。
跑完每遍kruskal后把白边的权值再减回去。
二分结束后，输出当前的实际权值。
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXE 100005
#define MAXV 50005
using namespace std;
int v, e, need;
struct node {
int fr, to, w, col;
friend bool operator < (const node &a, const node &b) {
return (a.w == b.w) ? (a.col < b.col) : (a.w < b.w);
}
} edge[MAXE];
int l = -101, r = 101, mid, ans = 0, res = 0;
int fa[MAXV];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int kruskal(int mid) {
int sum_edge = 0, sum_white = 0;
res = 0;
for (int i = 1; i <= v; i++) fa[i] = i;
for (int i = 1; i <= e; i++) {
if (!edge[i].col)
edge[i].w += mid;
}
sort(edge + 1, edge + e + 1);
for (int i = 1; i <= e; i++) {
int x = find(edge[i].fr), y = find(edge[i].to);
if (x != y) {
fa[x] = y;
res += edge[i].w;
sum_edge++;
if (!edge[i].col)
sum_white++;
}
if (sum_edge == v - 1)
break;
}
for (int i = 1; i <= e; i++) {
if (!edge[i].col)
edge[i].w -= mid;
}
return sum_white;
}
int main() {
scanf("%d%d%d", &v, &e, &need);
for (int i = 1; i <= e; i++) {
scanf("%d%d%d%d", &edge[i].fr, &edge[i].to, &edge[i].w, &edge[i].col);
edge[i].fr++, edge[i].to++;
}
while (l <= r) {
mid = (l + r) >> 1;
if (kruskal(mid) >= need) {
l = mid + 1;
ans = res - mid * need;
} else
r = mid - 1;
}
printf("%d\n", ans);
return 0;
}