§ 题意简述

这个题面很友好。

§ 题解

二分+最小生成树。

我们可以给每条白边加上某一个值。这样就可以使得我们求最小生成树的时候，可以控制白边选择的数量。

显然我们可以二分这个值。

下面给出单调性证明：

如果某一时刻的mid较大，使得选择的白边数量小于need，我们就相应的把mid调小，也就是令r=mid。

同理，如果某一时刻的mid较小，使得选择的白边数量大于，我们就相应的把mid调大，也就是令l=mid+1。

由上可知此题的单调性。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 100000 + 5;
const int INF = 1e2 + 5;
int n, m, ans, need;
struct EdgeNode {
	int from;
	int to, val;
	int color;
} e[MAXN];

int sum, tot, white;
struct UnionFindSet{
	int fa[MAXN];

	void init(int lim) {
		for (int i = 1; i <= lim; ++i)
			fa[i] = i;
		sum = 0;
		tot = 0;
		white = 0;
	}

	int find(int x) {
		if (x ^ fa[x]) fa[x] = find(fa[x]);
		return fa[x];
	}

	void merge(int x, int y, int i) {
		x = find(x);
		y = find(y);
		if (x ^ y) {
			tot++;
			fa[x] = y;
			sum += e[i].val;
			white += (e[i].color ^ 1);
		}
	}
} ufs;

bool cmp(EdgeNode x, EdgeNode y) {
	return (x.val == y.val) ? (x.color < y.color) : (x.val < y.val);
}

void get_mst() {
	sort(e + 1, e + 1 + m, cmp);
	for (int i = 1; tot != n - 1; ++i) {
		// if (tot == n - 1) break;
		ufs.merge(e[i].from, e[i].to, i);
	}
}

void over(int x) {
	for (int i = 1; i <= m; ++i) if (e[i].color ^ 1) e[i].val -= x;
}

bool check(int x) {
	ufs.init(n + 1);
	for (int i = 1; i <= m; ++i) if (e[i].color ^ 1) e[i].val += x;
	get_mst();
	return white >= need;
}

signed main() {
	scanf("%d %d %d", &n, &m, &need);
	for (int i = 1; i <= m; ++i) {
		scanf("%d %d %d %d", &e[i].from, &e[i].to, &e[i].val, &e[i].color);
		e[i].from++, e[i].to++;
	}
	int l = -INF, r = INF;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid + 1, ans = sum - mid * need;
		else r = mid;
		over(mid);
	}
	printf("%d\n", ans);
	return 0;
}