Description

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

　　题目保证有解。

 

Input

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

　　接下来E行

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

 

Output

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

 

Sample Input

2 2 1

0 1 1 1

0 1 2 0

Sample Output

2

HINT

 

数据规模和约定

　　0:V<=10

　　1,2,3:V<=15

　　0,..,19:V<=50000,E<=100000

　　所有数据边权为[1,100]中的正整数。

orz 王梦迪大神

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int N=50010; 5 struct ee{
    int x,y,w,c;}e[N*2]; 6 int fa[N]; 7 int ans,E,V,need,tot; 8 int root(int x){ 9     if(fa[x]==x) return x;10     fa[x]=root(fa[x]);return fa[x];11 }12  13 bool cmp(ee a,ee b){14     if(a.w==b.w) return a.c
        
         >1;37         for (int i=1;i<=E;i++) if(e[i].c==0)e[i].w+=mid;38         sort(e+1,e+1+E,cmp);39         int h=kls();40         if(h>=need) ans=(tot-need*mid),l=mid+1;else r=mid-1;41     //ans这里要注意一下，1wa42         for (int i=1;i<=E;i++) if(e[i].c==0)e[i].w-=mid;43     }44     printf("%d",ans);45 }