给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。

题目保证有解。

输入

第一行$V$,$E$,$need$分别表示点数，边数和需要的白色边数。

接下来$E$行,每行$s$,$t$,$c$,$col$表示这边的端点(点从$0$开始标号)，边权，颜色($0$白色$1$黑色)。

输出

一行表示所求生成树的边权和。

$V<=50000$,$E<=100000$,所有数据边权为$[1,100]$中的正整数。

样例输入

2 2 1
0 1 1 1
0 1 2 0

样例输出

2

本人代码

#include <bits/stdc++.h>
using namespace std;
const int N = 50005, M = 1000005;
int fa[N];

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

struct Edge {
	int u, v, w, f;
}g[M];

bool cmp1(Edge a, Edge b) {
	if (a.f < b.f)
		return 1;
	if (a.f > b.f)
		return 0;
	return a.w < b.w;
}

bool cmp2(Edge a, Edge b) {
	return a.w < b.w;
}

int n, m, ne;

int main() {
	scanf("%d%d%d", &n, &m, &ne);
	for (int i = 1; i <= m; i ++) {
		int s, t, c, col;
		scanf("%d%d%d%d", &s, &t, &c, &col);

		g[i].u = s, g[i].v = t, g[i].w = c, g[i].f = col;
	}



	for (int i = 0; i < n; i ++)
		fa[i] = i;

	int ans = 0;
	sort(g + 1, g + m + 1, cmp1);// 先选择need条白色边

//	for (int i = 1; i <= m; i ++) {
//	cout << g[i].u << ' ' << g[i].v << ' ' << g[i].w << ' ' << g[i].f << endl;
//	}
//    return 0;
	int cnt = 0;
	for (int i = 1; i <= m; i ++) {
		int x = find(g[i].u), y = find(g[i].v);
		if (x != y) {
			fa[x] = y;
			cnt ++;
			ans += g[i].w;
		}

		if (cnt == ne)
			break;
	}

	sort(g + 1, g + m + 1, cmp2);// 选择剩下的边

	for (int i = 1; i <= m; i ++) {
		int x = find(g[i].u), y = find(g[i].v);
		if (x != y) {
			fa[x] = y;
			ans += g[i].w;
		}
	}

	printf("%d\n", ans);

	return 0;
}
/*
2 2 1
0 1 1 1
0 1 2 0
*/