一开始以为先取need条最短的白边就行了。。然而那样子的话可能图根本没法联通= =
网上题解讲的挺清晰的。。就是二分把全部白边加上mid，然后看mst里面有多少条白边。有need条白边的时候再把加上的值减去，就是答案了。
但可能出现取不了need条白边的情况（二分mid取到>need条，二分mid+1时取到<need条）
这时候就是因为图中有一些黑边和白边权值相同。。那显然我们取的是黑边还是白边是可以替换的。。
所以取到>=need条白边的时候就可以更新答案。注意权值相同的话优先先取白边
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=100233; 7 struct zs{ 8 int u,v,dis; 9 }e[maxn],e1[maxn];int t,t1; 10 int fa[maxn],id[maxn]; 11 int i,j,k,n,m,ans,a,b,c,d,now,l,r,mid; 12 13 int ra;char rx; 14 inline int read(){ 15 rx=getchar(),ra=0; 16 while(rx<'0'||rx>'9')rx=getchar(); 17 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra; 18 } 19 bool cmp(int a,int b){return e[a].dis==e[b].dis?a<b:e[a].dis<e[b].dis;} 20 inline int getfa(int x){return fa[x]!=x?fa[x]=getfa(fa[x]):x;} 21 inline int get(int x){ 22 register int i,sm=1,num0=0;now=0; 23 for(i=1;i<=t;i++)e[i].dis+=x; 24 for(i=1;i<=n;i++)fa[i]=i; 25 sort(id+1,id+1+m,cmp); 26 // for(i=1;i<=m;i++)printf("! %d %d--%d %d %d %d ",id[i],e[id[i]].u,e[id[i]].v,e[id[i]].dis,getfa(e[id[i]].u),getfa(e[id[i]].v)); 27 for(i=1;i<=m&&sm<n;i++) 28 if((a=getfa(e[id[i]].u))!=(b=getfa(e[id[i]].v))) 29 fa[a]=b,sm++, 30 num0+=id[i]<=t, 31 now+=e[id[i]].dis;//,printf(" %d ",id[i]); 32 33 for(i=1;i<=t;i++)e[i].dis-=x; 34 // printf(" x:%d num0:%d now:%d sm:%d ",x,num0,now,sm); 35 return num0; 36 } 37 int main(){register int i; 38 n=read(),m=read(),k=read(); 39 for(i=1;i<=m;i++){ 40 a=read()+1,b=read()+1,c=read(),d=read(); 41 if(d)e1[++t1]=(zs){a,b,c}; 42 else e[++t]=(zs){a,b,c}; 43 } 44 for(i=t+1;i<=m;i++)e[i]=e1[i-t]; 45 for(i=1;i<=m;i++)id[i]=i; 46 l=-101,r=101;ans=1002333333; 47 while(l<=r){ 48 mid=(l+r)/2;//printf(" %d -- %d ",l,r); 49 if(get(mid)>=k)ans=now-mid*k,l=mid+1; 50 else r=mid-1; 51 } 52 printf("%d ",ans); 53 return 0; 54 }