题目大意

给你一个有$n$个点$m$条边的无向带权连通图，每条边是黑色或白色

让你求一棵最小权的恰好有$need$条白色边的生成树

数据范围

$1\leqslant n\leqslant 50000,1\leqslant m\leqslant 100000$

边权为$[1,100]$中的正整数

题解

设$f(x)$为白色路径边权增加$x$之后最小生成树中白色路径的条数，可以发现$f(x)$是单调递减的

则我们可以二分$x$，使得满足条件之下的最小生成树

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,need,last,ans,sum,cnt;
int u[100050],v[100050],c[100050],col[100050],f[50050];
struct edge{int u,v,c,col;}e[100050];
inline int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
inline int cmp(edge a,edge b){return a.c==b.c?a.col<b.col:a.c<b.c;}

inline int check(int x){
    sum=cnt=0;
    For(i,1,n) f[i]=i;
    For(i,1,m){
        e[i]=(edge){u[i],v[i],c[i],col[i]};
        if (!e[i].col) e[i].c+=x;
    }
    sort(e+1,e+m+1,cmp);
    For(i,1,m){

        int fu=getf(e[i].u),fv=getf(e[i].v);
        if (fu!=fv){
            f[fu]=fv;sum+=e[i].c;
            if (!e[i].col) cnt++;
        }
    }
    return cnt>=need;
}

int main(){
    n=read(),m=read(),need=read();
    For(i,1,m) u[i]=read()+1,v[i]=read()+1,c[i]=read(),col[i]=read();

    int l=-100,r=100;
    while (l<=r){
        int mid=(l+r)>>1;
        if (check(mid)) l=mid+1,ans=sum-need*mid;
        else r=mid-1;
    }
    printf("%d\n",ans);    
    return 0;
}