分析
对于 kruskal 算法，是对边权排序，然后依次判环然后加边。
但是这里有是限制的，我们跑出来最小生成树不一定是有 n e e d need need 条白边的最小生成树。
那怎么办？
比如白边数量大于 n e e d need need，多余的白边是什么到前面去的？因为 kruskal 的排序，那么这下知道怎么解决了，我们统一将所有白边的权值加上一个数 x x x，白边的权值变大了，排序时后面的权值较小黑边就到了前面，这样就可以减少白边数量，最后再将在最小生成树中加上的白边的权值 n ⋅ n e e d n\cdot need n⋅need 减去就行了。
那么这个加上的值怎么求？
因为有可能白边数量过少，就需要加负数，所以最小值应该是 − 100 -100 −100 ，过多就加整数，最大值为 100 100 100 （见题目数据范围）
x x x 的值就在 − 100 -100 −100 到 100 100 100 之间，是线性且有序的，那么想到了什么？
二分。
实现
对 x x x 进行二分，然后将所有白边加上一个值 m i d mid mid ，包最小生成树，记录白边数量，如果大了就往大的二分，小了就往小的二分。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x<10){putchar(x+'0');return;}
print(x/10);
putchar(x%10+'0');
}
void putstr(string s){
for(int i=0;i<s.size();i++)putchar(s[i]);
}
int n,m,k;
int f[N];
int find(int x){
if(x!=f[x])f[x]=find(f[x]);
return f[x];
}
struct node{
int u,v,w,c;
};
node a[N];
bool cmp(node a,node b){
return a.w<b.w||(a.w==b.w&&a.c<b.c);
}
int ans;
int kru(){
sort(a+1,a+1+m,cmp);
int sum=0;
ans=0;
for(int i=1;i<=m;i++){
int u=a[i].u;
int v=a[i].v;
int w=a[i].w;
int c=a[i].c;
if(find(u)==find(v))continue;
f[find(u)]=find(v);
ans+=1-c;
sum+=w;
}
return sum;
}
signed main(){
//ios::sync_with_stdio(0);
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
int u=read()+1,v=read()+1,w=read(),c=read();
a[i]=node{u,v,w,c};
}
int l=-100,r=100;
int answer;
int mid;
while(l<r){
mid=l+r>>1;
for(int i=0;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)if(!a[i].c)a[i].w+=mid;
int sum=kru();
if(ans<k)r=mid-1;
else l=mid+1,answer=sum-k*mid;
for(int i=1;i<=m;i++)if(!a[i].c)a[i].w-=mid;
}
print(answer);
}