[关闭]
@ysner 2018-09-28T18:49:17.000000Z 字数 2979 阅读 1740

[bzoj3073]Journeys

线段树 线段树优化连边 最短路


题面

建造了一个很大的星球,他准备建造个国家和无数双向道路。个国家很快建造好了,用编号,但是他发现道路实在太多了,他要一条条建简直是不可能的!
于是他以如下方式建造道路:表示,对于任意两个国家,如果,那么在之间建造一条道路。保证一条道路不会修建两次,也保证不会有一个国家与自己之间有道路。
好不容易建好了所有道路,他现在在位于号的首都。想知道号国家到任意一个国家最少需要经过几条道路。当然,保证号国家能到任意一个国家。

解析

显然不能照着题面说的去建边啊,空间复杂度惹不起。
一般来说,当边数过多的时候,一般都有一种使边数变少的方法:线段树优化连边
:其实还有一种,在"[SDOI2010]所驼门王的宝藏"中,我是用把区间所有点连成一个环来表示区间点能够相互到达的,但这种只适用于判连通性)

首先要有两颗线段树,一颗维护出发区间,一颗维护到达区间。(要不然会重复)
如果要在对应的两个区间建边,可以建单向边,从一个区间(线段树)向一个新建点连边,边权赋为;再把这点连向另一个区间(线段树),边权赋为
如果要建反向边,再新建一个点就可以了。
(理性思考一下发现与题目意思是等价的)

在出发线段树内部,由子结点向父结点建边;在到达线段树内部,由父结点向子结点建边。边权均为。毕竟区间内部移动应该是(可看为)不需要经过道路的。
然后两颗线段树对应结点建边权为的双向边。

所以这个建边的空间复杂度是多少呢?
线段树内部建边,线段树对应点连边,区间建边
所以建边数组要使劲往大开。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<queue>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define ls x<<1
  12. #define rs x<<1|1
  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 N=1e7+100;
  17. int n,m,p,st[N],ed[N],id[2][N],tot,h[N],cnt,dis[N];
  18. bool vis[N];
  19. struct Edge{int to,nxt,w;}e[N];
  20. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
  21. struct node{int u,dis;il bool operator < (const node &o) const {return dis>o.dis;}};
  22. priority_queue<node>Q;
  23. il ll gi()
  24. {
  25. re ll x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void Build(re int x,re int l,re int r)
  33. {
  34. id[0][x]=++tot;id[1][x]=++tot;
  35. if(l==r)
  36. {
  37. st[l]=id[0][x];ed[l]=id[1][x];
  38. add(id[0][x],id[1][x],0);
  39. add(id[1][x],id[0][x],0);
  40. return;
  41. }
  42. re int mid=l+r>>1;
  43. Build(ls,l,mid);Build(rs,mid+1,r);
  44. add(id[0][ls],id[0][x],0);add(id[0][rs],id[0][x],0);
  45. add(id[1][x],id[1][ls],0);add(id[1][x],id[1][rs],0);
  46. }
  47. il void Insert(re int x,re int l,re int r,re int ql,re int qr,re int u,re int op)
  48. {
  49. if(ql<=l&&r<=qr)
  50. {
  51. if(!op) add(id[0][x],u,1);
  52. else add(u,id[1][x],0);
  53. return;
  54. }
  55. re int mid=l+r>>1;
  56. if(ql<=mid) Insert(ls,l,mid,ql,qr,u,op);
  57. if(qr>mid) Insert(rs,mid+1,r,ql,qr,u,op);
  58. }
  59. il void Dijstra()
  60. {
  61. memset(dis,63,sizeof(dis));
  62. Q.push((node){st[p],0});dis[st[p]]=0;
  63. while(!Q.empty())
  64. {
  65. re int u=Q.top().u;Q.pop();
  66. vis[u]=1;
  67. for(re int i=h[u];i;i=e[i].nxt)
  68. {
  69. re int v=e[i].to;
  70. if(dis[v]>dis[u]+e[i].w)
  71. {
  72. dis[v]=dis[u]+e[i].w;
  73. Q.push((node){v,dis[v]});
  74. }
  75. }
  76. while(!Q.empty()&&vis[Q.top().u]) Q.pop();
  77. }
  78. }
  79. int main()
  80. {
  81. n=gi();m=gi();p=gi();
  82. Build(1,1,n);
  83. fp(i,1,m)
  84. {
  85. re int A=gi(),B=gi(),C=gi(),D=gi();
  86. ++tot;
  87. Insert(1,1,n,A,B,tot,0);
  88. Insert(1,1,n,C,D,tot,1);
  89. ++tot;
  90. Insert(1,1,n,C,D,tot,0);
  91. Insert(1,1,n,A,B,tot,1);
  92. }
  93. Dijstra();
  94. fp(i,1,n) printf("%d\n",dis[ed[i]]);
  95. return 0;
  96. }

然而时间不够优秀。。。
注意到边权只有,我们实际上可以优化最短路算法中的那个
每次更新完,我们可以把为的放在队首,为的放在队尾。因为从转移过来的肯定比从的更优。

  1. il void Dijstra()
  2. {
  3. memset(dis,63,sizeof(dis));
  4. Q.push_back(st[p]);dis[st[p]]=0;
  5. while(!Q.empty())
  6. {
  7. re int u=Q.front();Q.pop_front();
  8. if(vis[u]) continue;vis[u]=1;
  9. for(re int i=h[u];i;i=e[i].nxt)
  10. {
  11. re int v=e[i].to;
  12. if(dis[v]>dis[u]+e[i].w)
  13. {
  14. dis[v]=dis[u]+e[i].w;
  15. e[i].w?Q.push_back(v):Q.push_front(v);
  16. }
  17. }
  18. }
  19. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注