[关闭]
@Bei-S 2019-01-10T07:19:22.000000Z 字数 2631 阅读 437

题解 P2387 【[NOI2014]魔法森林】

题解


我们都生活在阴沟里,但仍有人在仰望星空。——奥斯卡·王尔德


前天写了一下午+晚上运输计划结果到最后还是95,最后换种写法才A掉
然后昨天下午到今天上午一直在肝魔法森林,真的现在看到LCT就头大
这道一年前我觉得这辈子都不可能写的题终于被干掉了|>_<|

结合Bei-S's 博客食用更佳哦~

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=5e5+20;
  4. const int INF=0x7ffffff;
  5. int head[N],cnt,fa[N],p[N],son[N][2],id[N],mx[N],rev[N],val[N],siz[N],n,m,ans=INF;
  6. struct ii{
  7. int x,y,a,b;
  8. }e[N*2];
  9. inline bool isroot(int x){return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;}
  10. inline void pushdown(int x){
  11. if(!rev[x]) return ;
  12. rev[x]=0;rev[son[x][0]]^=1;rev[son[x][1]]^=1;
  13. swap(son[x][0],son[x][1]);
  14. }
  15. inline void pushup(int x){//更新最大边编号
  16. if(val[x]>val[id[son[x][0]]]&&val[x]>val[id[son[x][1]]]) id[x]=x;//如果当前点(边化的点)比儿子的边权都大,直接赋为x
  17. else id[x]=val[id[son[x][0]]]>val[id[son[x][1]]]?id[son[x][0]]:id[son[x][1]];//否则谁大赋谁的
  18. }
  19. inline void rotate(int x){
  20. pushdown(fa[x]);pushdown(x);
  21. int y=fa[x],z=fa[y],t=son[y][0]==x;
  22. if(!isroot(y)) son[z][y==son[z][1]]=x;
  23. fa[x]=z;
  24. son[y][!t]=son[x][t];fa[son[x][t]]=y;
  25. son[x][t]=y;fa[y]=x;
  26. pushup(y);pushup(x);
  27. }
  28. inline void splay(int x){
  29. pushdown(x);
  30. while(!isroot(x)){
  31. int y=fa[x],z=fa[y];
  32. if(!isroot(y)) (son[y][0]==x)^(son[z][0]==y)?rotate(x):rotate(y);
  33. rotate(x);
  34. }
  35. }
  36. inline void Access(int x){
  37. for(int y=0;x;y=x,x=fa[x]){
  38. splay(x);
  39. son[x][1]=y;
  40. pushup(x);
  41. }
  42. }
  43. inline void Makeroot(int x){
  44. Access(x);
  45. splay(x);
  46. rev[x]^=1;
  47. }
  48. inline void Split(int x,int y){
  49. Makeroot(x);
  50. Access(y);
  51. splay(x);
  52. }
  53. inline void Link(int x,int y){
  54. Makeroot(x);
  55. fa[x]=y;
  56. }
  57. inline void Cut(int x,int y){
  58. Split(x,y);
  59. splay(x);
  60. fa[y]=son[x][1]=0;
  61. }
  62. inline int Find(int x){
  63. Access(x);
  64. splay(x);
  65. while(son[x][0]) x=son[x][0];
  66. return x;
  67. }
  68. inline int sa(int x,int y){//查询x,y路径中b值最大的边的编号
  69. Makeroot(x);
  70. Access(y);
  71. splay(y);//把x,y放入一颗splay中,把y splay到根,更新后id[y]即为所求
  72. return id[y];
  73. }
  74. bool cmp(ii l,ii r) {return l.a<r.a;}
  75. int main(){
  76. scanf("%d%d",&n,&m);
  77. for(int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);
  78. sort(e+1,e+1+m,cmp);//按照a排序
  79. for(int i=1;i<=m;i++){
  80. int u=e[i].x,v=e[i].y,a=e[i].a,b=e[i].b;
  81. if(Find(u)==Find(v)){//如果边的端点已经连通,他们之间最大b值
  82. int f=sa(u,v);//f为U,V间最大(b值)边的编号
  83. if(val[f]<=b) {//如果val[f]<=b 直接查询即可
  84. if(Find(1)==Find(n))
  85. ans=min(ans,a+val[sa(1,n)]);
  86. continue;
  87. }
  88. Cut(f,e[f-n].x);Cut(f,e[f-n].y);//否则我们需要删去这条边,注意删去后记得连边,我写在下面了
  89. }
  90. val[i+n]=b;//如果 端点不连通 或者 新加入边的b值比边的端点间最大的b值小 ,我们都要连上这条边
  91. id[i+n]=i+n;//把边化点,val记为b,id记作i+n
  92. Link(u,i+n);Link(v,i+n);
  93. if(Find(1)==Find(n))//更新答案
  94. ans=min(ans,a+val[sa(1,n)]);
  95. }
  96. cerr<<ans;
  97. if(ans==INF) printf("-1");
  98. else printf("%d",ans);
  99. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注