```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int v,e,need;
const int maxv=1e5+5;
const int maxe=1e6+5;
int cnt;
int ans;
int sum;
int fa[maxv];
inline int read ()
{
int x = 0 , f = 1;
char ch = getchar();
while ( !isdigit ( ch ) ) { if ( ch == '-' ) f = -1; ch = getchar (); }
while ( isdigit ( ch ) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar (); }
return x * f;
}
int find(int x){
if(fa[x]==x){
return x;
}
else{
return fa[x] = find(fa[x]);
}
}
struct node{
int u,v,w,col;
}a[maxe];
bool cmp(node a,node b){
if(a.w!=b.w){
return a.w<b.w;
}
else{
return a.col<b.col;
}
}
void kruskal(int x){
for(int i=1;i<=v;i++){
fa[i]=i;
}
sum=0;
cnt=0;
for(int i=1;i<=e;i++){
a[i].w+=(a[i].col^1)*x;
}
sort(a+1,a+1+e,cmp);
for(int i=1;i<=e;i++){
int ax=find(a[i].u);
int bx=find(a[i].v);
if(ax!=bx){
if(a[i].col==0){
cnt++;
}
fa[ax]=bx;
sum+=a[i].w;
}
}
for(int i=1;i<=e;i++){
a[i].w-=(a[i].col^1)*x;
}
}
signed main()
{
// freopen("a.in","r",stdin);
v=read();
e=read();
need=read();
for(int i=1;i<=v;i++){
fa[i]=i;
}
for(int i=1;i<=e;i++){
int s,t,c,col;
s=read();
t=read();
c=read();
col=read();
a[i].u=s+1;
a[i].v=t+1;
a[i].w=c;
a[i].col=col;
}
int l=-200;
int r=200;
int mid;
while(l<=r){
mid=l+r>>1;
kruskal(mid);
if(cnt>=need){
l=mid+1;
}
else{
r=mid-1;
}
}
kruskal(r);
cout<<sum-need*r;
return 0;
}
```
by Dr_Octopus @ 2023-03-16 10:07:58
@[Dr_Octopus](/user/883403) 膜膜膜
by Zimo_666 @ 2023-03-16 10:09:23
@[Dr_Octopus](/user/883403) 感谢大佬qwq
by fchwpo @ 2023-03-16 10:09:52
此帖完结qwq
by fchwpo @ 2023-03-16 10:11:15
考古。
by fchwpo @ 2023-07-20 17:07:44