P2619

就是WQS二分 改得跟题解几乎一模一样了 还是80分

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50009;
const int M=100009;
struct edge{
	int u,v,w;
	bool tag;
}e[M];
bool cmp(const edge&a,const edge&b){
    return a.w<b.w;
}
int n,m,k;
int fa[N];
int find(int x){
	while(fa[x]!=x) x=fa[x]=fa[fa[x]];
    return x;
}
bool ok(int x){
	for(int i=0;i<m;i++)
		if(!e[i].tag) e[i].w+=x;
	for(int i=1;i<=n;i++) fa[i]=i;
	int cnt=0,rcnt=0;
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++){
        int fx=find(e[i].u),fy=find(e[i].v);
        if(fx==fy) continue;
        if(cnt++==n-1) break;
        fa[fx]=fy;
        if(!e[i].tag) rcnt++;
    }
	for(int i=0;i<m;i++)
		if(!e[i].tag) e[i].w-=x;
	return rcnt>=k;
}
int main(){
	cin>>n>>m>>k;
	for(int i=0;i<m;i++) cin>>e[i].u>>e[i].v>>e[i].w>>e[i].tag;
	for(int i=0;i<m;i++) e[i].u++,e[i].v++;
	int l=-100,r=100,a=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(ok(mid)){
			a=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	for(int i=0;i<m;i++)
		if(!e[i].tag) e[i].w+=a;
	for(int i=1;i<=n;i++) fa[i]=i;
	int ans=0,cnt=0;
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++){
        int fx=find(e[i].u),fy=find(e[i].v);
        if(fx==fy) continue;
        if(cnt++==n-1) break;
        fa[fx]=fy;
        ans+=e[i].w;
    }
    cout<<ans-k*a<<endl;
	return 0;
}