代码如下

#include <cstdio>
#include <algorithm>
using namespace std;

int n , m , k , f[50005] , ans;

struct edge
{
	int x , y , w , c;
}e[100005];

bool cmp(edge x , edge y)
{
	return x.w < y.w;
}

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

void merge(int x , int y)
{
	x = find(x);
	y = find(y);
	f[x] = y;
}

int main()
{
	scanf("%d%d%d" , &n , &m , &k);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d%d" , &e[i].x , &e[i].y , &e[i].w , &e[i].c);
		e[i].x++;
		e[i].y++;
	}
	int l = -1000 , r = 1000;
	while (l <= r)
	{
		int mid = (l + r) / 2;
		for (int i = 1; i <= m; i++) if (!e[i].c) e[i].w += mid;
		sort(e + 1 , e + m + 1 , cmp);
		for (int i = 1; i <= n; i++) f[i] = i;
		int cnt = 0 , sum = 0;
		for (int i = 1; i <= m; i++)
			if (find(e[i].x) != find(e[i].y))
			{
				sum += e[i].w;
				merge(e[i].x , e[i].y);
				if (!e[i].c) cnt++;
			}
		for (int i = 1; i <= m; i++) if (!e[i].c) e[i].w -= mid;
		if (cnt >= k)
		{
			ans = sum - mid * k;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	printf("%d\n" , ans);
	
	return 0;
}

孩子要疯了！！！