[关闭]
@Jerusalem 2016-02-04T10:59:54.000000Z 字数 2451 阅读 1334

Solution

Vol 2


SDOI2011 消防

BZOJ2282

题目是给出了一棵树,要求树上的一段路径,让这段路径的长度小于等于某个定值S,并使所有不在路径上的点到路径的距离的最大值最小。

直觉上,我们可以二分这个距离,然后对于每个点维护与它距离不超过这么多的点集,这显然是一棵树,最后将所有点的树求交。

这可以用LCT完成……虽然考虑到代码量,这算法想想就好。

直觉告诉我,不是省选压轴题的本题,标算不可能这么SXBK……

这道题要优化的目标,很直观地会让我们猜测它必然和直径有关系。

一个命题:对任意直径,必然存在一个最优化方案,使该路径落在直径上。

首先,如果一个最优化方案与直径交集为空,考虑把它“扯”到直径上,减去覆盖部分后我们会发现,直径的一部分不如最优方案的一部分长,这与直径的定义矛盾。用类似的方法,可以证明它必然落在直径上。

然后用一个简单的单调队列就可以了。

这道题网络上流传的解法主要是在直径上二分……这是可以卡的。

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <vector>
  8. #include <queue>
  9. using namespace std;
  10. struct Edge{
  11. int from,to,w;
  12. Edge(){
  13. from=to=0;
  14. w=0;
  15. }
  16. Edge(int from_,int to_,int w_){
  17. from=from_,to=to_;
  18. w=w_;
  19. }
  20. };
  21. const int maxn=300005,INF=0x3f3f3f3f;
  22. vector<Edge> G[maxn];
  23. int next[maxn];
  24. int NextW[maxn];
  25. int DiameterFrom;
  26. int OnDiameter[maxn];
  27. deque<int> Q;
  28. int pre[maxn];
  29. int MaxDis[maxn];
  30. int cnt;
  31. int n,S;
  32. namespace GetDiameter{
  33. int dis[maxn];
  34. int GetFar(int u,int f)
  35. {
  36. int ans=u;
  37. for(int i=0;i<G[u].size();i++){
  38. Edge e=G[u][i];
  39. if(e.to==f)
  40. continue;
  41. int tot=GetFar(e.to,u);
  42. if(dis[e.to]+e.w>dis[u])
  43. ans=tot,dis[u]=dis[e.to]+e.w;
  44. }
  45. return ans;
  46. }
  47. void DfsDiameter(int u,int f)
  48. {
  49. next[u]=-1;
  50. for(int i=0;i<G[u].size();i++){
  51. Edge e=G[u][i];
  52. if(e.to==f)
  53. continue;
  54. DfsDiameter(e.to,u);
  55. if(dis[e.to]+e.w>dis[u])
  56. dis[u]=dis[e.to]+e.w,next[u]=e.to,NextW[u]=e.w;
  57. }
  58. }
  59. void Solve()
  60. {
  61. memset(dis,0,sizeof(dis));
  62. DiameterFrom=GetFar(1,-1);
  63. memset(dis,0,sizeof(dis));
  64. DfsDiameter(DiameterFrom,-1);
  65. memset(OnDiameter,false,sizeof(OnDiameter));
  66. int u=DiameterFrom;
  67. while(u!=-1){
  68. OnDiameter[u]=true;
  69. u=next[u];
  70. }
  71. }
  72. }
  73. void Dfs(int u,int f)
  74. {
  75. for(int i=0;i<G[u].size();i++){
  76. Edge e=G[u][i];
  77. if(e.to==f||OnDiameter[e.to])
  78. continue;
  79. Dfs(e.to,u);
  80. MaxDis[u]=max(MaxDis[u],MaxDis[e.to]+e.w);
  81. }
  82. }
  83. void First()
  84. {
  85. GetDiameter::Solve();
  86. int u=DiameterFrom;
  87. while(u!=-1){
  88. Dfs(u,-1);
  89. if(next[u]!=-1)
  90. pre[next[u]]=pre[u]+NextW[u];
  91. cnt=u;
  92. u=next[u];
  93. }
  94. }
  95. void Solve()
  96. {
  97. int ans=INF;
  98. int l=DiameterFrom,r=l;Q.push_back(l);
  99. int p=-1;
  100. while(l!=-1){
  101. if(Q.front()==p)
  102. Q.pop_front();
  103. while(next[r]!=-1&&pre[next[r]]-pre[l]<=S){
  104. while(!Q.empty()&&MaxDis[Q.back()]<MaxDis[next[r]])
  105. Q.pop_back();
  106. Q.push_back(next[r]);
  107. r=next[r];
  108. }
  109. ans=min(ans,max(max(pre[l],pre[cnt]-pre[r]),MaxDis[Q.front()]));
  110. p=l;
  111. l=next[l];
  112. }
  113. cout<<ans<<endl;
  114. }
  115. void AddEdge(int u,int v,int w)
  116. {
  117. G[u].push_back(Edge(u,v,w));
  118. G[v].push_back(Edge(v,u,w));
  119. }
  120. void ReadData()
  121. {
  122. scanf("%d%d",&n,&S);
  123. for(int i=1;i<n;i++){
  124. int u,v,w;
  125. scanf("%d%d%d",&u,&v,&w);
  126. AddEdge(u,v,w);
  127. }
  128. }
  129. void Freopen()
  130. {
  131. freopen("loli.in","r",stdin);
  132. }
  133. void Close()
  134. {
  135. fclose(stdin);
  136. fclose(stdout);
  137. }
  138. int main()
  139. {
  140. Freopen();
  141. ReadData();
  142. First();
  143. Solve();
  144. Close();
  145. return 0;
  146. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注