[关闭]
@ysner 2018-09-26T10:56:26.000000Z 字数 1348 阅读 1601

[国家集训队2]Tree I

二分 生成树


题面

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

解析

好像有个套路:
对于有个数要求的某种边,可以改变它们的权值,以改变它们加入最小生成树的顺序(包括移出最小生成树)。
改变量可以二分。因为改变量(包括符号)越大,加入的边就越少。

细节:

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define db double
  11. #define eps 1e-5
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=1e5+100;
  16. int n,m,k,f[N];
  17. ll ans;
  18. bool use[N];
  19. 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];
  20. il ll gi()
  21. {
  22. re ll x=0,t=1;
  23. re char ch=getchar();
  24. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  25. if(ch=='-') t=-1,ch=getchar();
  26. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  27. return x*t;
  28. }
  29. il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
  30. il int check(re int x)
  31. {
  32. re ll tag=0,tot=0;ans=0;
  33. fp(i,1,n) f[i]=i;
  34. fp(i,1,m)
  35. {
  36. a[i]=b[i];
  37. if(!a[i].t) a[i].w+=x;
  38. }
  39. sort(a+1,a+1+m);
  40. fp(i,1,m)
  41. {
  42. re int u=find(a[i].u),v=find(a[i].v);
  43. if(u^v) f[v]=u,ans+=a[i].w,tag+=(a[i].t==0),++tot;
  44. }
  45. return tag>=k;
  46. }
  47. int main()
  48. {
  49. n=gi();m=gi();k=gi();
  50. fp(i,1,m)
  51. {
  52. a[i].u=gi()+1,a[i].v=gi()+1,a[i].w=gi();a[i].t=gi();
  53. b[i]=a[i];
  54. }
  55. re int l=-105,r=105,gu=0;
  56. while(l<=r)
  57. {
  58. re db mid=l+r>>1;
  59. if(check(mid)) gu=mid,l=mid+1;
  60. else r=mid-1;
  61. }
  62. check(gu);
  63. printf("%lld\n",ans-gu*k);
  64. return 0;
  65. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注