BZOJ2654 tree 題解（最小生成樹+二分答案）

傳送門

考慮直接求一個最小生成樹，取到的白邊數量可能會多于need條或者少于need條，這取決于白邊的邊權大小。

是以為了取need條白邊，我們可以嘗試給白邊的邊權都加上一個值。

白邊的邊權越大，出現在最小生成樹中的白邊就越少，是以答案滿足很好的單調性，考慮二分答案 m i d mid mid，給所有白邊的邊權都加上 m i d mid mid，然後求最小生成樹，看看取到的白邊數量夠不夠 n e e d need need條。

#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>

template <typename T> inline void read(T& t) {
    int f = 0, c = getchar(); t = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
    if (f) t = -t;
}
template <typename T> inline bool chkMin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkMax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
#ifdef WIN32
#define LLIO "%I64d"
#else
#define LLIO "%lld"
#endif	// WIN32 long long
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (A); I >= (B); --I)
#define erep(I, X) for (int I = head[X]; I; I = next[I])

const int maxn = 5e4 + 207, maxm = 1e5 + 207;
struct Edge {
    int x, y, w, c;
};
Edge e[maxm];
int fa[maxn];
int n, m, need, sum;
inline bool operator<(const Edge& lhs, const Edge& rhs) {
    return lhs.w < rhs.w || (lhs.w == rhs.w && lhs.c < rhs.c);
}
int findf(int x) { return x == fa[x] ? x : fa[x] = findf(fa[x]); }
inline bool check(int mid) {
    rep(i, 1, m) if (!e[i].c) e[i].w += mid;
    std::sort(e + 1, e + m + 1);
    rep(i, 1, n) fa[i] = i;
    int cnt = sum = 0;
    rep(i, 1, m) {
        int fx = findf(e[i].x), fy = findf(e[i].y);
        if (fx ^ fy) {
            fa[fx] = fy;
            sum += e[i].w;
            cnt += !e[i].c;
        }
    }
    rep(i, 1, m) if (!e[i].c) e[i].w -= mid;
    return cnt >= need;
}
int main() {
    read(n); read(m); read(need);
    rep(i, 1, m) {
        read(e[i].x); read(e[i].y); read(e[i].w); read(e[i].c);
        ++e[i].x; ++e[i].y;
    }
    int left = -101, right = 101, pos;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (check(mid)) left = (pos = mid) + 1;
        else right = mid - 1;
    }
    check(pos);
    printf("%d\n", sum - need * pos);
    return 0;
}