[关闭]
@ysner 2018-08-09T12:11:42.000000Z 字数 1813 阅读 1664

视察

贪心


题面

给一棵树,要求在选取的点与点之间,距离不小于的前提下,最大化点的数量。

解析

贪心原则是:随便找个点为根,用堆维护当前深度最大的点,选取它作为答案之一,然后把离他距离小于的点删掉,依此类推。
证明???
我只能猜这是因为深度越大,选取该点对选取其它点影响越小。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<queue>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int mod=1e9+7,N=1e6+100;
  17. struct Edge{int to,nxt,w;}e[N<<1];
  18. int in[N],h[N],cnt,n,t,ans,tot,d[N],pos,mx;
  19. bool vis[N];
  20. struct node{int dis,u;bool operator < (const node &o) const {return dis<o.dis;}};
  21. priority_queue<node>Q;
  22. il void add(re int u,re int v,re int w)
  23. {
  24. e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;
  25. }
  26. il ll gi()
  27. {
  28. re ll x=0,t=1;
  29. re char ch=getchar();
  30. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  31. if(ch=='-') t=-1,ch=getchar();
  32. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  33. return x*t;
  34. }
  35. il void pre(re int u,re int fa)
  36. {
  37. d[u]=d[fa]+1;if(d[u]>mx) mx=d[u],pos=u;
  38. for(re int i=h[u];i+1;i=e[i].nxt)
  39. {
  40. re int v=e[i].to;
  41. if(v==fa) continue;
  42. pre(v,u);
  43. }
  44. }
  45. il void dfs(re int u,re int fa,re int dd)
  46. {
  47. Q.push((node){dd,u});
  48. for(re int i=h[u];i+1;i=e[i].nxt)
  49. {
  50. re int v=e[i].to;
  51. if(v==fa) continue;
  52. dfs(v,u,dd+e[i].w);
  53. }
  54. }
  55. il void find(re int u,re int fa,re int dis)
  56. {
  57. //printf("%d %d %d\n",u,fa,dis);
  58. if(dis<t) vis[u]=1;else return;
  59. for(re int i=h[u];i+1;i=e[i].nxt)
  60. {
  61. re int v=e[i].to;
  62. if(v==fa) continue;
  63. find(v,u,dis+e[i].w);
  64. }
  65. }
  66. il void solve()
  67. {
  68. while(!Q.empty())
  69. {
  70. while(!Q.empty()&&vis[Q.top().u]) Q.pop();
  71. if(!Q.empty())
  72. {
  73. re int u=Q.top().u;Q.pop();++ans;//printf("%d\n",u);
  74. find(u,u,0);
  75. }
  76. }
  77. }
  78. int main()
  79. {
  80. freopen("inspect.in","r",stdin);
  81. freopen("inspect.out","w",stdout);
  82. memset(h,-1,sizeof(h));
  83. n=gi();t=gi();
  84. fp(i,1,n-1)
  85. {
  86. re int u=gi(),v=gi(),w=gi();
  87. add(u,v,w);add(v,u,w);in[u]++;in[v]++;
  88. }
  89. pre(1,0);
  90. dfs(pos,pos,0);
  91. solve();
  92. printf("%d\n",ans);
  93. fclose(stdin);
  94. fclose(stdout);
  95. return 0;
  96. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注