[BZOJ3073][PA2011]Journeys(最短路径,线段树)

发布于 2018-05-08  144 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3073][PA2011]Journeys(最短路径,线段树)

Description

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号国家能到任意一个国家。

Tag

最短路径,线段树

解决思路

如果数据范围小一点的话,那么这就是最短路径的题。但由于是区间连边,最坏情况下边数可能到达爆炸的$$O(n^2m)$$,所以考虑优化连边。
由区间可以想到处理区间的利器——线段树。对于双向路径$(a,b)-(c,d)$,我们把它拆成两条单向的路径。对于每一组$(a,b)->(c,d)$,我们新建立一个虚点$node$,然后考虑如何建图。
单个一棵线段树是无法处理双向边的问题的,不妨建立两棵线段树,一棵成为出线段树,即$(a,b)->node$,反之,另一颗为入线段树。建边如下。
首先是线段树上的建边。对于出线段树,从儿子指向父亲,表示若能到达儿子,则也能到达父亲,权为0;对于入线段树,从父亲指向儿子,表示若能到达父亲,也能到达儿子,权为0;另外再从入线段树的点直到对应出线段树的节点,权为0。
然后是$$(a,b)->(c,d)$$。在出线段树上找到$(a,b)$对应的$log$个区间,分别从这些区间连到$node$,权为$1$;再在入线段树上找到$(c,d)$对应的$log$个区间,从$node$连边到这些区间,权为$0$。
然后跑最短路,最后的答案就在每一个点对应的第一棵线段树的节点上。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define lson (now<<1)
#define rson (lson|1)

const int maxN=501000;
const int maxQ=101000;
const int maxNode=((maxN<<2)+(maxQ<<1))<<1;
const int maxM=maxNode*10;
const int inf=2147483647;

class HeapData
{
public:
    int u,dist;
};

int n,m,P;
int Id1[maxN],Id2[maxN],nodesum,nodecnt;
int edgecnt=0,Head[maxNode],Next[maxM],V[maxM],W[maxM];
bool vis[maxNode];
int Dist[maxNode];
priority_queue<HeapData> H;

bool operator < (HeapData A,HeapData B);
void Add_Edge(int u,int v,int w);
void Build1(int now,int l,int r);
void Build2(int now,int l,int r);
void Add1(int now,int l,int r,int ql,int qr,int node,int opt);
void Add2(int now,int l,int r,int ql,int qr,int node,int opt);

int main()
{
    mem(Head,-1);
    scanf("%d%d%d",&n,&m,&P);
    Build1(1,1,n);Build2(1,1,n);//建树
    nodecnt=nodesum<<1;
    for (int i=1;i<=m;i++)
    {
        int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
        nodecnt++;
        Add1(1,1,n,a,b,nodecnt,0);
        Add2(1,1,n,c,d,nodecnt,1);
        nodecnt++;
        Add1(1,1,n,c,d,nodecnt,0);
        Add2(1,1,n,a,b,nodecnt,1);
    }
    mem(Dist,-1);P=Id1[P];Dist[P]=0;H.push((HeapData){P,0});
    do
    {
        int u=H.top().u;H.pop();
        if (vis[u]) continue;
        vis[u]=1;
        for (int i=Head[u];i!=-1;i=Next[i])
            if ((vis[V[i]]==0)&&((Dist[V[i]]==-1)||(Dist[V[i]]>Dist[u]+W[i])))
            {
                Dist[V[i]]=Dist[u]+W[i];
                H.push((HeapData){V[i],Dist[V[i]]});
            }
    }
    while (!H.empty());
    for (int i=1;i<=n;i++) printf("%d\n",Dist[Id1[i]]);
    return 0;
}

bool operator < (HeapData A,HeapData B)
{
    return A.dist>B.dist;
}

void Add_Edge(int u,int v,int w)
{
    //cout<<"Add:"<<u<<"->"<<v<<" "<<w<<endl;
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
}

void Build1(int now,int l,int r)
{
    if (l==r){
        Id1[l]=now;nodesum=max(nodesum,now);return;
    }
    int mid=(l+r)>>1;
    Add_Edge(lson,now,0);Add_Edge(rson,now,0);
    Build1(lson,l,mid);Build1(rson,mid+1,r);
    return;
}

void Build2(int now,int l,int r)
{
    Add_Edge(now+nodesum,now,0);
    if (l==r){
        Id2[l]=now+nodesum;return;
    }
    int mid=(l+r)>>1;
    Add_Edge(now+nodesum,lson+nodesum,0);Add_Edge(now+nodesum,rson+nodesum,0);
    Build2(lson,l,mid);Build2(rson,mid+1,r);
    return;
}

void Add1(int now,int l,int r,int ql,int qr,int node,int opt)
{
    if ((l==ql)&&(r==qr))
    {
        if (opt==0) Add_Edge(now,node,1);
        else Add_Edge(node,now,0);
        return;
    }
    int mid=(l+r)>>1;
    if (qr<=mid) Add1(lson,l,mid,ql,qr,node,opt);
    else if (ql>=mid+1) Add1(rson,mid+1,r,ql,qr,node,opt);
    else
    {
        Add1(lson,l,mid,ql,mid,node,opt);
        Add1(rson,mid+1,r,mid+1,qr,node,opt);
    }
    return;
}

void Add2(int now,int l,int r,int ql,int qr,int node,int opt)
{
    if ((l==ql)&&(r==qr))
    {
        if (opt==0) Add_Edge(now+nodesum,node,1);
        else Add_Edge(node,now+nodesum,0);
        return;
    }
    int mid=(l+r)>>1;
    if (qr<=mid) Add2(lson,l,mid,ql,qr,node,opt);
    else if (ql>=mid+1) Add2(rson,mid+1,r,ql,qr,node,opt);
    else
    {
        Add2(lson,l,mid,ql,mid,node,opt);
        Add2(rson,mid+1,r,mid+1,qr,node,opt);
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3073][PA2011]Journeys(最短路径,线段树)


HNCJ OIer