2654: tree

Time Limit: 30 Sec  Memory Limit: 512 MB

Submit: 2733  Solved: 1124

[][][]

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

 

Source

 

[ ][ ][ ]

一种叫WQS二分的思想，据说[九省联考2018]林克卡特树用到了这个东西。

但是这道题不看论文也可以直接做，将每条白边加上x后求MST，设树上的白边的个数为f(x)，可以确定f(x)是单调不增的，二分即可。

但可能f(mid)>k,f(mid+1)<k，我们把相同长度的白边放在黑边的前面即可。

1 #include
     
       2 #include
      
        3 #define rep(i,l,r) for (int i=l; i<=r; i++) 4 typedef long long ll; 5 using namespace std; 6  7 const int N=100100; 8 int n,m,cnt,tot,k,ans,u[N],v[N],w[N],c[N],fa[N]; 9 struct E{ int u,v,w,c; }e[N];10 11 bool operator<(E a,E b){ return a.w==b.w ? a.c
       
        =k;30 }31 32 int main(){33     scanf("%d%d%d",&n,&m,&k);34     rep(i,1,m) scanf("%d%d%d%d",&u[i],&v[i],&w[i],&c[i]),u[i]++,v[i]++;35     int L=-105,R=105;36     while(L<=R){37         int mid=(L+R)>>1;38         if(check(mid)) L=mid+1,ans=tot-k*mid; else R=mid-1;39     }40     printf("%d\n",ans);41     return 0;42 }