[关闭]
@Venous 2018-02-22T22:08:26.000000Z 字数 4129 阅读 1007

2018.2.6 队列+次小生成树

考试


本次考试排名:Rank23
本次考试题目推荐:数字游戏(细节巨多),麦乐鸡翅(可后悔堆)
板子:次小生成树(数据较弱)
今天没有心路历程(Angry),要加油了
对自己算作一次警告


1.数字游戏

题面描述

认识到了游泳的巨大安全隐患之后,小朋友们都决定不去游泳了。于是,游泳馆冷清了下来。为了能因时制宜、因事制宜,游泳馆决定在游泳项目之外,还开设头脑风暴项目。头脑风暴当中有这样一道题目:给出一个LEN位的数字A,你可以删除数字A当中的N位,删除之后得到一个LEN-N位的数字B,你的目标就是使这个数字B最小。

数据范围

对于 50%的数据,LEN<=100000.
对于 100%的数据,LEN<=5000000 , 0<=N<=LEN.

解法

利用单调栈,从前往后尽力去维护递增,只要仍有删除次数就维护下去。说白了是贪心即可(每次删除左边第一个比右边大的)

好了,上代码

  1. int Max=cnt-N;
  2. for(int i=1;i<=cnt;i++)
  3. {
  4. while(a[i]<zhan[top]&&N&&top)
  5. top--,N--;
  6. zhan[++top]=a[i];
  7. }
  8. bool flag=0;
  9. for(int i=1;i<=top&&i<=Max;i++)
  10. {
  11. if(!flag&&!zhan[i])continue;
  12. flag=1;
  13. printf("%d",zhan[i]);
  14. }
  15. if(!flag)puts("0");

2.麦乐鸡翅

题面描述

在太行山路上,有一家麦乐鸡翅的生意火爆。因为好吃,所以卖的特别好。排队的人就特别多,经常有很多人买不到鸡翅。鸡翅会在每分钟烤出个,每分钟也只会卖给一个客人,第i个客人需要买个。因为生意火爆,老板可以选择在这分钟不卖给这个客人鸡翅,或者卖给这个顾客他需要的鸡翅,如果现在剩余的鸡翅不够,那就肯定不能卖给这个客人。无论这个客人能否买到鸡翅,他必须离开队伍。现在给定 N 分钟,且已经知道每分钟烤出的鸡翅个数,也知道每个客人需要鸡翅的个数,现在老板想知道,如何合理安排卖给与拒绝,最多可以满足多少人

数据范围

50% 数据保证 N<=1000
100% 1<=N<=250000 Xi,Yi 都在[0,10^9]范围内

解法

弄一个大根堆出来,然后后悔就OK了,甚是简单(那你怎么不现切)

  1. rg ll sum=0,now;
  2. for(rg int i=1;i<=n;i++)
  3. {
  4. sum+=a[i];
  5. if(!chi.empty())now=chi.top();
  6. if(sum>=b[i])
  7. {
  8. sum-=b[i];
  9. chi.push(b[i]);
  10. }
  11. else if(b[i]<now)
  12. {
  13. sum+=now-b[i];
  14. chi.pop();
  15. chi.push(b[i]);
  16. }
  17. }
  18. rg int ans=chi.size();
  19. cout<<ans<<endl;

3.次小生成树

题面描述

小 C 最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。 正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无向图的次小生成树,而且这个次小生成树还得是严格次小的,也就是说:如果最小生成树选择的边集是EM,严格次小生成树选择的边集是 ES,那么需要满足:(value(e) 表示边 e 的权值)

数据范围

数据中无向图无自环;
50% 的数据 N≤2 000 M≤3 000;
80% 的数据 N≤50 000 M≤100 000;
100% 的数据 N≤100 000 M≤300 000 ,边权值非负且不超过 10^9 。

解法

最小生成树与次小生成树一定只有一条边的长度不同(证明感性思考一下就好了),因而我们要先构出一棵最小生成树,然后再从边集中选入某条边以此来代替最小生成树上的边。由于我们新加入的边所连接的两点x,y必定是在同一个集合中的了,因而我们考虑将x->y路径上某条边断掉,那么为了使修改后的边权和尽可能接近最小生成树的边权和,我们查询x->y路径上的最大值,因而这个可以用倍增或树剖+线段树完成(笔者用的是倍增)
但是!!!(这个题目这么简单就太天真了!)会存在如下情况
有多组最小生成树满足条件
因而我们还需要维护一个次大值,在有多组最大满足下输出次大就好了!这样是不是可以解决问题了!好了,还有一些细节要处理,笔者放在代码里了,希望对大家有帮助(这个题目要思想有思想,要难度有难度,要细节有细节)

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. #define rg register
  7. #define ll long long
  8. #define inf 1e18
  9. const int MAXN=3e5+5;
  10. int N,M;
  11. ll ans=inf,s;
  12. inline int read()
  13. {
  14. rg char ch='!';rg int z=1,num=0;
  15. while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  16. if(ch=='-')z=-1,ch=getchar();
  17. while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
  18. return z*num;
  19. }
  20. struct edge{int x,y,z,pd;}e[MAXN];
  21. inline bool cmp(edge A,edge B)
  22. {
  23. if(A.z!=B.z)return A.z<B.z;
  24. if(A.x!=B.x)return A.x<B.x;
  25. return A.y<B.y;
  26. }
  27. int bcj[MAXN];
  28. int find(int x)
  29. {
  30. if(bcj[x]!=x)bcj[x]=find(bcj[x]);
  31. return bcj[x];
  32. }
  33. struct hand{int to,next,w;}a[MAXN<<1];
  34. int head[MAXN],cnt,tot;
  35. inline void link(int u,int v,int z)
  36. {
  37. a[++cnt]=(hand){v,head[u],z};
  38. head[u]=cnt;
  39. }
  40. int dep[MAXN],f[MAXN][26];
  41. ll g1[MAXN][26],g2[MAXN][26];
  42. void dfs(int u,int fa)
  43. {
  44. for(rg int i=head[u];i;i=a[i].next)
  45. {
  46. rg int v=a[i].to;
  47. if(v==fa)continue;
  48. f[v][0]=u;
  49. g1[v][0]=a[i].w;
  50. g2[v][0]=-inf;
  51. dep[v]=dep[u]+1;
  52. dfs(v,u);
  53. }
  54. }
  55. inline void Kru()
  56. {
  57. rg int cao=0;
  58. for(rg int i=1;i<=M;i++)
  59. {
  60. rg int x=e[i].x,y=e[i].y;
  61. rg int dx=find(x),dy=find(y);
  62. if(dx!=dy)
  63. {
  64. bcj[dy]=dx;
  65. e[i].pd=1;
  66. cao++;
  67. s+=e[i].z;
  68. link(y,x,e[i].z);
  69. link(x,y,e[i].z);
  70. }
  71. if(cao==N-1)break;
  72. }
  73. }
  74. inline void match(int &u,int j,ll &maxx,ll &semx)
  75. {
  76. if(maxx>g1[u][j])
  77. {
  78. semx=max(semx,g1[u][j]);
  79. }
  80. else if(maxx<g1[u][j])
  81. {
  82. semx=max(maxx,g2[u][j]);
  83. maxx=g1[u][j];
  84. }
  85. else
  86. {
  87. semx=max(semx,g2[u][j]);
  88. }
  89. u=f[u][j];
  90. }
  91. inline ll Lca(int u,int v,int stand)
  92. {
  93. if(dep[u]<dep[v])swap(u,v);
  94. rg int cha=dep[u]-dep[v];
  95. rg ll maxx=-inf,semx=-inf;
  96. for(rg int j=20;j>=0;j--)
  97. {
  98. if((1<<j)&cha)
  99. match(u,j,maxx,semx);
  100. }
  101. if(u==v)
  102. {
  103. if(maxx==stand){return semx;}
  104. return maxx;
  105. }
  106. for(rg int j=20;j>=0;j--)
  107. {
  108. if(f[u][j]!=f[v][j])
  109. {
  110. match(u,j,maxx,semx);
  111. match(v,j,maxx,semx);
  112. }
  113. }
  114. match(u,0,maxx,semx);match(v,0,maxx,semx);
  115. if(semx==-inf)return -inf;
  116. if(maxx==stand)return semx;
  117. return maxx;
  118. }
  119. int main()
  120. {
  121. //freopen("pai.in","r",stdin);
  122. //freopen("a.out","w",stdout);
  123. N=read();M=read();
  124. for(rg int i=1;i<=M;i++)e[i]=(edge){read(),read(),read()};
  125. for(rg int i=1;i<=N;i++)bcj[i]=i;
  126. sort(e+1,e+M+1,cmp);
  127. for(rg int i=0;i<=20;i++)g1[1][i]=g2[1][i]=-inf;
  128. Kru();dep[1]=1;dfs(1,0);
  129. for(rg int j=1;j<=20;j++)
  130. {
  131. for(rg int i=1;i<=N;i++)
  132. {
  133. f[i][j]=f[f[i][j-1]][j-1];
  134. g1[i][j]=max(g1[i][j-1],g1[f[i][j-1]][j-1]);
  135. if(g1[i][j-1]!=g1[f[i][j-1]][j-1])
  136. {
  137. g2[i][j]=min(g1[i][j-1],g1[f[i][j-1]][j-1]);
  138. }
  139. else
  140. {
  141. g2[i][j]=max(g2[i][j-1],g2[f[i][j-1]][j-1]);
  142. }
  143. }
  144. }
  145. rg int x,y;
  146. for(rg int i=1;i<=M;i++)
  147. {
  148. if(e[i].pd)continue;
  149. x=e[i].x,y=e[i].y;
  150. ans=min(ans,s-Lca(x,y,e[i].z)+e[i].z);
  151. }
  152. cout<<ans<<endl;
  153. return 0;
  154. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注