# 萌新求助

@胡子 2018-10-21 15:06 回复

rt，努力调试，只有40，两眼一闭，菜到安详QAQ

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 200010
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;++i)
using namespace std;

int n,m,c,t,x,y,z,num,need,l,r,mid,anss;
struct hz{
int from;
int to;
int dis;
int mode;
bool operator <(const hz &o)const{
if(dis+(mode==0?mid:0)==o.dis+(o.mode==0?mid:0))
return mode<o.mode;
return dis+(mode==0?mid:0)<o.dis+(o.mode==0?mid:0);
}
}h[maxn];

inline void in(int &x){
x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c==-1) return;
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x=x*f;
}

inline void out(int a){
if(a<0){
a*=-1;
putchar('-');
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}

int father(int x){
if(f[x]!=x) f[x]=father(f[x]);
return f[x];
}

bool pd(int a,int b){
int fa=father(a);
int fb=father(b);
//    cout<<"fa是"<<fa<<" "<<"fb是"<<fb<<endl;
if(fa!=fb)
return true;
return false;
}

void merge(int a,int b){
int fa=father(a);
int fb=father(b);
f[fa]=fb;
}

bool check(){ //判断白边是否小于要求的个数
FOR(i,0,n)
f[i]=i;
sort(h+1,h+m+1);
cnt[0]=cnt[1]=0;
FOR(i,1,m){
if(pd(h[i].from,h[i].to)){
//          cout<<h[i].from<<" "<<h[i].to<<endl;
merge(h[i].from,h[i].to);
++cnt[h[i].mode];
}
if(cnt[0]+cnt[1]==n-1)
break;
}
if(cnt[0]>=need)
return true;
return false;
}

int main(){
in(n),in(m),in(need);
FOR(i,1,m){
in(h[i].from),in(h[i].to),in(h[i].dis),in(h[i].mode);
}
l=-200;r=200;
while(l<=r){
mid=(l+r)>>1;
if(check()){
l=mid+1;
c=mid;
}
else
r=mid-1;
}
//  cout<<mid<<endl;
//  FOR(i,1,m)
//    cout<<h[i].from<<" "<<h[i].to<<" "<<h[i].dis<<" "<<h[i].mode<<endl;
anss=0;
int res=0;
FOR(i,0,n)
f[i]=i;
mid=c;
sort(h+1,h+m+1);
cnt[0]=cnt[1]=0;
FOR(i,1,m){
if(pd(h[i].from,h[i].to)){
if(cnt[0]==need&&h[i].mode==0) //奇怪的地方
continue;
merge(h[i].from,h[i].to);
anss+=h[i].dis;
cnt[h[i].mode]++;
++res;
}
if(res==n-1)
break;
}
out(anss);
}