#include<bits/stdc++.h>
using namespace std;
int s[1000010];
int n,m,need;
struct node{
	int s,t,w,c;
}e[1000010];
inline bool cmp(node a,node b){
	if(a.w==b.w) return a.c<b.c;
	else return a.w<b.w;
}
inline int find(int x){
	if(s[x]==x) return x;
	return s[x]=find(s[x]);
}
int sum,ans,temp;
int cnt=0;
inline void kruskal(){
	sort(e+1,e+1+m,cmp);
	for(int i=1;cnt!=n-1;i++){
		int xx=find(e[i].s),yy=find(e[i].t);
		if(xx==yy) continue;
		if(xx!=yy){
			cnt++;
			s[xx]=yy;
			if(e[i].c==0) temp++;
			sum+=e[i].w;
		} 
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&need);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&e[i].s,&e[i].t,&e[i].w,&e[i].c);
		e[i].s++;
		e[i].t++;
	}
	int l=-111,r=111;
	while(l<=r){
		int mid=(l+r)>>1;
		for(int i=1;i<=m;i++){
			if(e[i].c==0){
				e[i].w+=mid;
			}
		}
		for(int i=1;i<=n+1;i++){
			s[i]=i;
		}
		sum=0;
		cnt=0;
		temp=0;
		kruskal();
		if(temp>=need){
			l=mid+1;
			ans=sum-need*mid;
		}
		else r=mid-1;
		for(int i=1;i<=m;i++){
			if(e[i].c==0){
				e[i].w-=mid;
			}
		}	
	}
	printf("%d\n",ans);
	return 0;
}

二分答案加最小生成树

`