思路与算法

对白边额外加统一惩罚λ，按修改后边权运行Kruskal；修改权相同优先白边，使当前最优树的白边数最多。随着λ增加，所选白边数单调不增。在[-101,101]二分最大的仍能选到至少need白边的λ，最终答案为该修改后MST权和减去λ×need。

正确性说明

Kruskal正确求出每个λ的修改后最小权，平局优先白边给出其中最大白边数。比较两个惩罚值的最优性不等式可得白边数单调。生成树的交换性质使“恰有k白边的最小原权”形成离散凸序列，因此临界惩罚处可在并列最优树间通过等价交换实现need，修改后最优值减λneed即所求。原边权1至100，惩罚绝对值101足以在交换中优先最大或最小白边数，覆盖所有保证可行的need。

复杂度

每轮复制并排序E条边O(E log E)，并查集O(E α(V))；二分约8轮，加一次最终MST。总O(E log E log 203)，空间O(V+E)，初始化和每轮复制/并查集重置均已计入。原权和≤100(V-1)，用long long保存含惩罚的中间和。

易错点

col=0才是白边。平局必须先白，二分判定方向是白边数≥need向更大λ走。不能直接按原权贪心后修颜色。独立答案对小图枚举全部生成树；最大规模平行黑白链提供任意need的可行构造与精确闭式成本。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    vector<int> p, size;
    DSU(int n) : p(n), size(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (x != p[x]) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (size[a] < size[b])
            swap(a, b);
        p[b] = a;
        size[a] += size[b];
        return true;
    }
};
struct Edge {
    int u, v, c, col;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, need;
    cin >> n >> m >> need;
    vector<Edge> edges(m);
    for (auto &e : edges)
        cin >> e.u >> e.v >> e.c >> e.col;
    auto mst = [&](int penalty) {
        auto e = edges;
        sort(e.begin(), e.end(), [&](Edge a, Edge b) {
            int x = a.c + (a.col == 0 ? penalty : 0), y = b.c + (b.col == 0 ? penalty : 0);
            if (x != y)
                return x < y;
            return a.col < b.col;
        });
        DSU d(n);
        long long sum = 0;
        int whites = 0;
        for (auto x : e)
            if (d.join(x.u, x.v)) {
                sum += x.c + (x.col == 0 ? penalty : 0);
                whites += x.col == 0;
            }
        return make_pair(sum, whites);
    };
    int l = -101, r = 101;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        if (mst(mid).second >= need)
            l = mid;
        else
            r = mid - 1;
    }
    cout << mst(l).first - 1LL * l * need << '\n';
}