[bzoj3073]Journeys

https://www.zybuluo.com/ysner/note/1295471

题面

\(Seter\)建造了一个很大的星球，他准备建造\(N\)个国家和无数双向道路。\(N\)个国家很快建造好了，用\(1..N\)编号，但是他发现道路实在太多了，他要一条条建简直是不可能的！

于是他以如下方式建造道路：\((a,b),(c,d)\)表示，对于任意两个国家\(x,y\)，如果\(a<=x<=b,c<=y<=d\)，那么在\(xy\)之间建造一条道路。\(Seter\)保证一条道路不会修建两次，也保证不会有一个国家与自己之间有道路。

\(Seter\)好不容易建好了所有道路，他现在在位于\(P\)号的首都。\(Seter\)想知道\(P\)号国家到任意一个国家最少需要经过几条道路。当然，\(Seter\)保证\(P\)号国家能到任意一个国家。

\(n\leq5*10^5,m\leq10^6\)

解析

显然不能照着题面说的去建边啊，空间复杂度\(O(n^2)\)惹不起。

一般来说，当边数过多的时候，一般都有一种使边数变少的方法：线段树优化连边。

首先要有两颗线段树，一颗维护出发区间，一颗维护到达区间。（要不然会重复）

如果要在对应的两个区间建边，可以建单向边，从一个区间（线段树）向一个新建点连边，边权赋为\(1\)；再把这点连向另一个区间（线段树），边权赋为\(0\)。

如果要建反向边，再新建一个点就可以了。

（理性思考一下发现与题目意思是等价的）

在出发线段树内部，由子结点向父结点建边；在到达线段树内部，由父结点向子结点建边。边权均为\(0\)。毕竟区间内部移动应该是（可看为）不需要经过道路的。

然后两颗线段树对应结点建边权为\(0\)的双向边。

所以这个建边的空间复杂度是多少呢？

线段树内部建边\(O(2nlogn)\)，线段树对应点连边\(O(nlogn)\)，区间建边\(O(m*?)\)。

所以建边数组要使劲往大开。

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

#define re register

#define il inline

#define ls x<<1

#define rs x<<1|1

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=1e7+100;

int n,m,p,st[N],ed[N],id[2][N],tot,h[N],cnt,dis[N];

bool vis[N];

struct Edge{int to,nxt,w;}e[N];

il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}

struct node{int u,dis;il bool operator < (const node &o) const {return dis>o.dis;}};

priority_queue<node>Q;

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il void Build(re int x,re int l,re int r)

{

  id[0][x]=++tot;id[1][x]=++tot;

  if(l==r)

    {

      st[l]=id[0][x];ed[l]=id[1][x];

      add(id[0][x],id[1][x],0);

      add(id[1][x],id[0][x],0);

      return;

    }

  re int mid=l+r>>1;

  Build(ls,l,mid);Build(rs,mid+1,r);

  add(id[0][ls],id[0][x],0);add(id[0][rs],id[0][x],0);

  add(id[1][x],id[1][ls],0);add(id[1][x],id[1][rs],0);

}

il void Insert(re int x,re int l,re int r,re int ql,re int qr,re int u,re int op)

{

  if(ql<=l&&r<=qr)

    {

      if(!op) add(id[0][x],u,1);

      else add(u,id[1][x],0);

      return;

    }

  re int mid=l+r>>1;

  if(ql<=mid) Insert(ls,l,mid,ql,qr,u,op);

  if(qr>mid) Insert(rs,mid+1,r,ql,qr,u,op);

}

il void Dijstra()

{

  memset(dis,63,sizeof(dis));

  Q.push((node){st[p],0});dis[st[p]]=0;

  while(!Q.empty())

    {

      re int u=Q.top().u;Q.pop();

      vis[u]=1;

      for(re int i=h[u];i;i=e[i].nxt)

	{

	  re int v=e[i].to;

	  if(dis[v]>dis[u]+e[i].w)

	    {

	      dis[v]=dis[u]+e[i].w;

	      Q.push((node){v,dis[v]});

	    }

	}

      while(!Q.empty()&&vis[Q.top().u]) Q.pop();

    }

}

int main()

{

  n=gi();m=gi();p=gi();

  Build(1,1,n);

  fp(i,1,m)

    {

      re int A=gi(),B=gi(),C=gi(),D=gi();

      ++tot;

      Insert(1,1,n,A,B,tot,0);

      Insert(1,1,n,C,D,tot,1);

      ++tot;

      Insert(1,1,n,C,D,tot,0);

      Insert(1,1,n,A,B,tot,1);

    }

  Dijstra();

  fp(i,1,n) printf("%d\n",dis[ed[i]]);

  return 0;

}

然而时间不够优秀。。。

注意到边权只有\(0/1\)，我们实际上可以优化最短路算法中的那个\(log\)。

每次更新完，我们可以把为\(0\)的放在队首，为\(1\)的放在队尾。因为从\(0\)转移过来的肯定比从\(1\)的更优。

il void Dijstra()

{

  memset(dis,63,sizeof(dis));

  Q.push_back(st[p]);dis[st[p]]=0;

  while(!Q.empty())

    {

      re int u=Q.front();Q.pop_front();

      if(vis[u]) continue;vis[u]=1;

      for(re int i=h[u];i;i=e[i].nxt)

	{

	  re int v=e[i].to;

	  if(dis[v]>dis[u]+e[i].w)

	    {

	      dis[v]=dis[u]+e[i].w;

	      e[i].w?Q.push_back(v):Q.push_front(v);

	    }

	}

    }

}

巴特西

[bzoj3073]Journeys

https://www.zybuluo.com/ysner/note/1295471

题面

解析

最新文章

热门文章