[关闭]
@ysner 2018-09-26T19:35:44.000000Z 字数 1509 阅读 1949

CF125E MST Company

二分 生成树 图论


题面

求一种特殊的最小生成树。给定一个有个节点和条边的图,找出一个生成树满足从根节点直接连向其余节点的边要恰好条,在此条件下生成树的权值和最小。

解析

这道题思路和[国家集训队2]Tree I是一样的。
不过蒟蒻被卡细节了。。。

  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=5e5+100;
  16. int n,m,k,f[N],sta[N],top;
  17. bool use[N];
  18. struct dat{int u,v,w,t,id;bool operator < (const dat &o) const {return (w<o.w)||(w==o.w&&t<o.t);}}a[N<<1],b[N<<1];
  19. il ll gi()
  20. {
  21. re ll x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
  29. il int check(re int x,re int op)
  30. {
  31. re int tag=0;top=0;
  32. fp(i,1,n) f[i]=i;
  33. fp(i,1,m)
  34. {
  35. a[i]=b[i];
  36. if(!a[i].t) a[i].w+=x;
  37. }
  38. sort(a+1,a+1+m);
  39. fp(i,1,m)
  40. {
  41. re int u=find(a[i].u),v=find(a[i].v);
  42. if(u^v)
  43. {
  44. if(tag==k&&!a[i].t) continue;
  45. f[v]=u;tag+=(a[i].t==0);
  46. sta[++top]=a[i].id;
  47. }
  48. }
  49. if(!op) return tag>=k;
  50. else return tag;
  51. }
  52. int main()
  53. {
  54. n=gi();m=gi();k=gi();
  55. fp(i,1,m)
  56. {
  57. a[i].u=gi(),a[i].v=gi(),a[i].w=gi();a[i].t=(a[i].u!=1&&a[i].v!=1);a[i].id=i;
  58. b[i]=a[i];
  59. }
  60. re ll l=-1e5-5,r=1e5+5,gu=1e9;
  61. while(l<=r)
  62. {
  63. re db mid=l+r>>1;
  64. if(check(mid,0)) gu=mid,l=mid+1;
  65. else r=mid-1;
  66. }
  67. //printf("%d\n",check(gu,1));
  68. if(check(gu,1)!=k||top<n-1) return puts("-1"),0;
  69. printf("%d\n",n-1);
  70. fp(i,1,top) printf("%d ",sta[i]);puts("");
  71. return 0;
  72. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注