Description

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

题目保证有解。

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。

接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

一行表示所求生成树的边权和。

V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1

0 1 1 1

0 1 2 0

Sample Output

2

HINT

原数据出错，现已更新 by liutian,但未重测---2016.6.24

---

题解Here!

 

首先，我们知道不能直接选$need$条白色边。

为什么？请看下面这组数据：

Input:3 4 10 1 5 01 2 6 00 1 2 11 2 9 1Output:8

如果我们选了$need$条较小的白边，那么可能会影响黑边的选择。

那怎么做？

由于这是个生成树，考虑$Kruskal$的流程。

要想白边数目满足要求就要调整白边的位置。

二分一个白边权值偏移量$w$，每条白边的边权加上这个偏移量之后做$Kruskal$，并统计使用的白边数量。

如果大于$need$，则白边需要再向后移；

小于$need$白边需要前移，调整偏移量。

最后就可以得到答案。

附代码：

#include
       
        #include
        
         #include
         
          #define MAXN 100010using namespace std;int n,m,k,ans,fa[MAXN];struct Edge{    int u,v,w,colour;}a[MAXN],b[MAXN];inline int read(){	int date=0,w=1;char c=0;	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}	return date*w;}inline bool cmp(const Edge &p,const Edge &q){    if(p.w==q.w)return p.colour
          
           =k?true:false);}void work(){    int l=-100,r=100,mid,s;    while(l<=r){        mid=l+r>>1;        if(kruskal(mid)){s=ans-mid*k;l=mid+1;}        else r=mid-1;    }    printf("%d\n",s);}void init(){    n=read();m=read();k=read();    for(int i=1;i<=m;i++){        a[i].u=read();a[i].v=read();a[i].w=read();a[i].colour=read();        a[i].u++;a[i].v++;    }}int main(){    init();    work();    return 0;}