\(\mathcal{Description}\)

  Link.

  给一个 \(n\) 个点 \(m\) 条边的带权无向图，边有权值和黑白颜色，求恰选出 \(K\) 条白边构成的最小生成树。

  \(n\le5\times10^4\)，\(m\le10^5\)。

\(\mathcal{Solution}\)

  沉迷造题，好久没写题解了 qwq。

  本题是 WQS 二分的板题。记 \(f(x)\) 表示恰选 \(x\) 条白边构成的最小生成树，不难发现 \((x,f(x))\) 在坐标轴上构成下凸包。而 WQS 二分本质上是用一个一次函数切这个未知的凸包，判断切点横坐标与给定的 \(K\) 的大小关系调整二分斜率，继而求到最终答案。

  具体可以看 @CreeperLKF 大佬的这篇博客。

  实现上，可以分别用 std::vector 存黑边和白边，跑 Kruskal 的时候用两个指针类似归并排序地扫，就能去掉排序的 \(\log\) 了。记边权上限 \(w\)，复杂度 \(\mathcal O(m(\log m+\log w))\)。

#include <cstdio>
#include <vector>
#include <algorithm>

const int MAXN = 5e4;
int n, m, K;

struct Edge {
    int u, v, w;
    inline bool operator < ( const Edge t ) const { return w < t.w; }
};
std::vector<Edge> W, B;

struct DSU {
    int fa[MAXN + 5];
    inline void init ( const int n ) { for ( int i = 1; i <= n; ++ i ) fa[i] = i; }
    inline int find ( const int x ) { return x ^ fa[x] ? fa[x] = find ( fa[x] ) : x; }
    inline bool unite ( int x, int y ) {
        x = find ( x ), y = find ( y );
        return x ^ y ? fa[x] = y, true : false;
    }
} dsu;

inline int Kruskal ( const int mid, int& wuse ) {
    int ret = wuse = 0; dsu.init ( n );
    for ( int i = 0, j = 0, cnt = 0; cnt < n - 1; ) {
        if ( j == ( int ) B.size () || ( i ^ W.size () && W[i].w + mid <= B[j].w ) ) {
            if ( dsu.unite ( W[i].u, W[i].v ) ) ret += W[i].w + mid, ++ wuse, ++ cnt;
            ++ i;
        } else {
            if ( dsu.unite ( B[j].u, B[j].v ) ) ret += B[j].w, ++ cnt;
            ++ j;
        }
    }
    return ret;
}

int main () {
    scanf ( "%d %d %d", &n, &m, &K );
    for ( int i = 1, u, v, w, c; i <= m; ++ i ) {
        scanf ( "%d %d %d %d", &u, &v, &w, &c );
        ++ u, ++ v;
        if ( ! c ) W.push_back ( { u, v, w } );
        else B.push_back ( { u, v, w } );
    }
    std::sort ( W.begin (), W.end () );
    std::sort ( B.begin (), B.end () );
    int l = -100, r = 100, ans = -1;
    while ( l <= r ) {
        int mid = l + r >> 1, curs, curw;
        curs = Kruskal ( mid, curw );
        if ( curw >= K ) l = mid + 1, ans = curs - mid * K;
        else r = mid - 1;
    }
    printf ( "%d\n", ans );
    return 0;
}