题目链接——洛谷（精确涉及到了WQS二分）
BZOJ-2654（不推荐）
个人不推荐做BZOJ2654的这道题，因为那道题可以水过去，不用WQS二分也是可以的，可以直接二分答案，显然是没有这个好的。
先在这里讲一下什么是WQS二分吧，也是从网上看来的，一开始在做这道题的时候，想到的也是存在这种可能性，但是依然WA了几次：
先说题意：给你一个N个点M条边无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有K条白色边的生成树。
然后WQS二分：也就是在黑边与白边存在相等的时候，我们直接二分的话，是得不到答案的，这时候就是需要去进行处理了，就有可能去取了“实际价值”更大的白边，而没有去取现实价值更小的黑边；或者现实价值更大的黑边、“实际价值”更小的白边。
举个例子，我们现在对所有白边（先不要管为什么“加一个数”）统一加上一个值，然后，（譬如说是“+(-5)”）出现值变成「1(0)，1(0)，1(0)，1(0)，1(1)，1(1)，1(1)」，但是我们只需要四条边，两条白边即可，我们会很自然的选择前4条边，但是出现了4条白边的情况；再看（现在到了“+(-4)”），出现值变成「2(0)，2(0)，2(0)，2(0)，1(1)，1(1)，1(1)」，此时我们会拿3条黑边和1条白边的形式了。
遇到上面这个形式应该怎么办呢，当“+(-5)”的情况的时候，其实我们就是得到了我们想要的答案了，因为需要两条白边，所以我们4 - (2 * (-5)) = 14就是我们要的答案了。（这就是WQS二分的解决办法QAQ）
其实在这种情况下，我们固定了白边（因为上限是确定的），然后黑边因为等同于此时的“假定”白边，所以，我们实际上做了一个用黑边代替白边的过程。
那么，上面讲到“对所有白边统一加一个数”，这是为什么呢？
可以看到，当对所有白边的边权-INF的时候，能取尽可能多的白边了，同理的，对所有白边的边权+INF的时候，取到的白边就会尽可能的少了，条件是限行的，所以，我们可以这样二分答案去满足条件。
一组测试样例：
6 8 3
0 1 2 1
0 2 10 0
1 3 4 1
1 4 30 0
2 5 4 0
1 2 4 0
3 4 5 1
4 5 5 1
ans:27
My Code：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxE = 1e5 + 7, maxN = 5e4 + 7;
int N, M, need, line[2] = {0}, root[maxN], MST_ans;
int fid(int x) { return x == root[x] ? x : root[x] = fid(root[x]); }
struct Eddge
{
int u, v, w, add;
Eddge(int a=0, int b=0, int c=0, int d=0):u(a), v(b), w(c), add(d) {}
friend bool operator < (Eddge e1, Eddge e2) { return e1.w < e2.w; }
}E[2][maxE];
inline void init() { for(int i=0; i<=N; i++) root[i] = i; }
bool flag = false;
inline bool Kruskal()
{
init(); MST_ans = 0;
int i = 1, j = 1, bian = 0, u, v, white = 0;
while(i <= line[0] || j <= line[1])
{
if(bian == N - 1) break;
if(j > line[1] || (i <= line[0] && E[0][i].w + E[0][i].add <= E[1][j].w))
{
u = fid(E[0][i].u); v = fid(E[0][i].v);
if(u != v)
{
MST_ans += E[0][i].w + E[0][i].add;
root[u] = v;
white++;
bian++;
}
i++;
}
else
{
u = fid(E[1][j].u); v = fid(E[1][j].v);
if(u != v)
{
MST_ans += E[1][j].w;
root[u] = v;
bian++;
}
j++;
}
}
return white >= need;
}
int main()
{
scanf("%d%d%d", &N, &M, &need);
for(int i=1, u, v, w, op; i<=M; i++)
{
scanf("%d%d%d%d", &u, &v, &w, &op);
E[op][++line[op]] = Eddge(u, v, w, 0);
}
sort(E[0] + 1, E[0] + line[0] + 1);
sort(E[1] + 1, E[1] + line[1] + 1);
int l = -100, r = 100, mid, ans = 0;
while(l <= r)
{
mid = (l + r) / 2;
for(int i=1; i<=line[0]; i++) E[0][i].add = mid;
if(Kruskal())
{
l = mid + 1;
ans = MST_ans - need * mid;
}
else
{
r = mid - 1;
}
}
if(!flag) printf("%d\n", ans);
return 0;
}
