# 求助wa3个点

@Twinkle_M 2019-02-27 21:02 回复
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
int u;
int v;
int w;
int col;
} e[5000055],a[5000055];
int n,m,k;
bool cmp(const node&x,const node&y)
{
return x.w<y.w;
}
int l,r;
int fa[5000005];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
int minn;
bool check(int x)
{
int need=0;
int ans=0;
int num=0;
for(int i=1;i<=m;i++)
{
a[i]=e[i];
if(a[i].col==0)
a[i].w+=x;
}
sort(a+1,a+1+m,cmp);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
int u=find(a[i].u);
int v=find(a[i].v);
if(u==v)
continue;
num++;
fa[u]=v;
ans+=a[i].w;
if(a[i].col==0)
need++;
if(n-1==num)
break;
}
minn=ans;
if(need>=k)
return 1;
return 0;
}
int main() {
cin>>n>>m>>k;
for(int i=1; i<=m; i++) {
int x,y,z,d;
scanf("%d%d%d%d",&x,&y,&z,&d);
e[i].u=x+1;
e[i].v=y+1;
e[i].w=z;
e[i].col=d;
}
l=-100;
r=100;
int wzx;
while(l<=r) {
int mid=(l+r)>>1;
if(check(mid))
l=mid+1,wzx=mid;
else
r=mid-1;
}
check(wzx);
//  cout<<ans<<" "<<minn<<endl;
cout<<minn-k*wzx<<endl;
return 0;
}