[国家集训队2]Tree I

https://www.zybuluo.com/ysner/note/1294263

题面

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

题目保证有解。

\(n\leq5*10^4,m\leq10^5\)

解析

好像有个套路：

对于有个数要求的某种边，可以改变它们的权值，以改变它们加入最小生成树的顺序（包括移出最小生成树）。

改变量可以二分。因为改变量（包括符号）越大，加入的边就越少。

细节：

答案并不一定会出现在二分的判定中，所以要最后对答案单独计算一次。
在边权相同时，要优先加入白色边。

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define ll long long

#define re register

#define il inline

#define db double

#define eps 1e-5

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=1e5+100;

int n,m,k,f[N];

ll ans;

bool use[N];

struct dat{int u,v,w,t;bool operator < (const dat &o) const {return (w<o.w)||(w==o.w&&t<o.t);}}a[N<<1],b[N<<1];

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}

il int check(re int x)

{

  re ll tag=0,tot=0;ans=0;

  fp(i,1,n) f[i]=i;

  fp(i,1,m)

    {

      a[i]=b[i];

      if(!a[i].t) a[i].w+=x;

    }

  sort(a+1,a+1+m);

  fp(i,1,m)

    {

      re int u=find(a[i].u),v=find(a[i].v);

      if(u^v) f[v]=u,ans+=a[i].w,tag+=(a[i].t==0),++tot;

    }

  return tag>=k;

}

int main()

{

  n=gi();m=gi();k=gi();

  fp(i,1,m)

    {

      a[i].u=gi()+1,a[i].v=gi()+1,a[i].w=gi();a[i].t=gi();

      b[i]=a[i];

    }

  re int l=-105,r=105,gu=0;

  while(l<=r)

    {

      re db mid=l+r>>1;

      if(check(mid)) gu=mid,l=mid+1;

      else r=mid-1;

    }

  check(gu);

  printf("%lld\n",ans-gu*k);

  return 0;

}

巴特西

[国家集训队2]Tree I

https://www.zybuluo.com/ysner/note/1294263

题面

解析

最新文章

热门文章