【一本通提高篇最小生成树】Tree

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Edge{
	int s,e,w,col;
	bool operator<(Edge x) const{
		if(x.w==w)return col<x.col;
		return w<x.w;
 	}
} a[100086];
int fa[100086],v,e,need,s,t,c,col;
inline int find(int x){
	if(fa[x]==x)return x;
	return fa[x] = find(fa[x]);
}
pair<int,int> check(int x){
	int ans=0,ned=0;
	for(int i=0;i<v;i++)fa[i]=i;
	for(int i=0;i<e;i++){
		if(a[i].col == 0)a[i].w += x;
	} 
	sort(a,a+e);
	for(int i=0;i<e;i++){
		int fs=find(a[i].s),fu=find(a[i].e);
		if(fs!=fu){
			fa[fs] = fu;
			ans += a[i].w;
			if(a[i].col == 0) ned++;
		}
	}
	for(int i=0;i<e;i++){
		if(a[i].col == 0)a[i].w -= x;
	}
	return make_pair(ans,ned);
}
signed main(){
	scanf("%lld%lld%lld",&v,&e,&need);
	for(int i=0;i<e;i++){
		scanf("%lld%lld%lld%lld",&s,&t,&c,&col);
		a[i] = {s,t,c,col};
	}
	int l=-1000,r=1000;
	while(l<r){
		int mid=l+r>>1;
		int t = check(mid).second;
		if(t<need)l = mid+1;
		else r = mid;
	}
	printf("%lld",check(l).first);
	return 0;
}