Luogu

分析

设 $f(x)$ 为恰好选 $x$ 条白边的答案。容易发现 $f(x)$ 是凹的。

考虑 WQS 二分。二分斜率 $m$，则我们需要最小化截距 $b=f(x)-mx$。

把每条白边的权值减去 $m$ 即可求出 $b$ 的最小值，再根据此时最多选出的白边数调整二分上下界即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10,M=100000+10;

int n,m,k;
struct edge { int u,v,w,c; } e[M];
bool operator <(edge a,edge b) { return a.w<b.w||(a.w==b.w&&a.c<b.c); }

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

pair<int,int> calc(int mid) {
    for (int i=1;i<=m;++i)
        if (!e[i].c) e[i].w-=mid;
    sort(e+1,e+m+1);
    for (int i=1;i<=n;++i) f[i]=i;
    int cntw=0,ans=0;
    for (int i=1;i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (find(u)!=find(v)) {
            cntw+=!e[i].c,ans+=e[i].w;
            f[find(u)]=find(v);
        }
    }
    for (int i=1;i<=m;++i)
        if (!e[i].c) e[i].w+=mid;
    return make_pair(cntw,ans);
}

int main() {
    n=read(),m=read(),k=read();
    for (int i=1;i<=m;++i) e[i]=(edge){read()+1,read()+1,read(),read()};
    int L=-100,R=100;
    while (L<R) {
        int mid=(L+R)>>1;
        if (calc(mid).first>=k) R=mid;
        else L=mid+1;
    }
    printf("%d\n",calc(L).second+k*L);
    return 0;
}