bzoj 2654: tree

Description

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

Solution

把边的集合看成一个序列,按照边权排序之后跑 \(kruskal\),就会从某个前缀中选择 \(n-1\) 条边
实际上这 \(n-1\) 条边中的白边不等于 \(need\) 条
如果把白边的边权同时扩大 \(mid\) ,那么白边之间的顺序是不变的,而白边相当于黑边整体右移了一些
我们要做的就是在向右(左)移动尽量少的情况下,使得白边为 \(need\) 条
最后边权和就是:最小生成树的边权和-\(need*mid\)
这个东西有单调性,二分这个 \(mid\) 来移动即可

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,ne,fa[N],ans=1e9;
inline int gi(){
    register char ch=getchar();register int str=0;
    while(ch>'9' || ch<'0')ch=getchar();
    while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
    return str;
}
struct node{
    int x,y,c,col,cf;
    inline bool operator <(const node &p)const{
        if(cf!=p.cf)return cf<p.cf;
        return col<p.col;
    }
}e[N];
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline bool check(int mid){
    for(int i=1;i<=m;i++)e[i].cf=e[i].col?e[i].c:e[i].c+mid;
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(e+1,e+m+1);
    int cr=0,tot=0,cnt=0;
    for(int i=1;i<=m;i++){
        int x=e[i].x,y=e[i].y;
        if(find(x)==find(y))continue;
        fa[find(y)]=find(x);
        cr+=e[i].col^1;tot+=e[i].cf;
        cnt++;
        if(cnt==n-1)break;
    }
    tot-=ne*mid;
    if(cr>=ne)return ans=tot,1;
    return 0;
}
int main(){
  freopen("pp.in","r",stdin);
  freopen("pp.out","w",stdout);
  cin>>n>>m>>ne;
  for(int i=1;i<=m;i++)e[i]=(node){gi()+1,gi()+1,gi(),gi(),0};
  int l=-101,r=101,mid;
  while(l<=r){
      mid=(l+r)>>1;
      if(check(mid))l=mid+1;
      else r=mid-1;
  }
  cout<<ans<<endl;
  return 0;
}

bzoj 2654: tree

原文：https://www.cnblogs.com/Yuzao/p/8570473.html