\(Description\)

给定一个无向带权连通图，每条边是黑色或白色。求一棵最小权的恰好有K条白边的生成树。

\(Solution\)

Kruskal是选取最小的n-1条边。而白边数有限制，考虑为其设额外边权C。

随着C增大，选的白边数应是不增的。可以二分求一个C值使得此时恰好选择K条边。选取时应优先选白边，因为多了还可以用黑边替换，少了只能减少C。

可能的问题是，C=mid时白边数>K，C=mid+1时白边数<K，因为有很多黑边与+mid后的白边权值想等。可以用这些黑边替换掉多余的白边，所以答案应是减K*mid(保留黑边)。

//404ms 3.36MB#include 
    
     #include 
     
      #include 
      
       //#define gc() getchar()#define MAXIN 100000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)const int N=5e4+5,M=1e5+5;int n,m,K,fa[N],Ans;char IN[MAXIN],*SS=IN,*TT=IN;int read();struct Edge{    int fr,to,val,col;    inline void Init(){        fr=read()+1, to=read()+1, val=read(), col=read();    }    bool operator <(const Edge &x)const{        return val==x.val?col
       
        
         >1)) l=mid+1;        else r=mid-1;//  Check(l);    printf("%d",Ans);    return 0;}