CF786B Legacy（线段树优化建图+最短路）

女爷i 2023-06-05 12:48 33阅读 0赞

在qbxt某营集体做的

题解里以及外地OIer基本上都写两颗线段树的

而我们六安的OIer神TM思维一致——只用一颗线段树，类似于一维分层图的思想，第二层上与第一层相对应的结点的编号是第一层结点编号+NUM，而且貌似比分颗的思维正常一点，因为满足lson=k<<1,rson=k<<1|1，和一般的线段树相似度高。

至于为什么要分颗或分层，容易想明白树边（辅助边）必须是双向的（因为要用祖先结点的出入信息），但如果不分颗或分层的话求出来最短路不很明显是0了吗QwQ

所以分层的话父向子应是一层，子向父应在另一层，两层之间通过叶节点相连

另外关于叶结点的处理问题，YoOXiii和Pride205是把原图第i结点投影到树上第i+n结点（n为原图结点个数）

这个详见他们的代码（其实我也没仔细研究清楚他们的处理方法），这里不偷了（偷窃犯罪w），要看自己找

由于我和他们不坐一块，想思路时没有交流，所以我没有这样写，我是把第一层按照一般线段树的编号建，这样容易一点。然后把原图结点直接向叶子结点映射即可（开一个pos数组）（才知道szsz46也是这么写的，原来六安OIer的思维同步性不随空间改变QwQ）

然后......

上代码吧

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<iostream>
    #define NUM 1000000
    #define maxn 100005<<5
    //这两个范围要调好 
    #define int long long
    using namespace std;
    typedef long long ll;
    
    inline void input(ll &x){
        ll ans=0,f=1;
        char c=getchar();
        while(c>'9'||c<'0'){
            if(c=='-')f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            ans=ans*10+c-48;
            c=getchar();
        }
        x=ans*f;
    }
    
    inline void output(ll x){
        if(x<0)x=-x,putchar('-');
        if(x>9)output(x/10);
        putchar(x%10+48);
    }
    
    inline void writeln(ll x){
        output(x);
        putchar('\n');
    }
    
    int n,m,s,head[maxn],c[maxn],pos[maxn],vis[maxn],dis[maxn],cnt;
    
    //pos:题中结点在树上的编号 
    
    struct edge{
        int v,w,next;
    }e[maxn];
    
    struct node{
        int dis,u;
        bool operator<(const node &x)const{return x.dis<dis;}
    };
    
    inline void add(int u,int v,int w){
        e[++cnt].v=v;
        e[cnt].w=w;
        e[cnt].next=head[u];
        head[u]=cnt;
    //  cout<<u<<' '<<v<<' '<<w<<endl;
    }
    
    inline void build(int k,int l,int r){
        if(l==r){
            pos[l]=k;
            add(k+NUM,k,0);
            add(k,k+NUM,0);
            return;
        }
        int mid=(l+r)>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        add(k<<1,k,0);
        add(k<<1|1,k,0);
        add(k+NUM,(k<<1)+NUM,0);//调了一个小时：加括号；在括号外加NUM而不是给k加NUM 
        add(k+NUM,(k<<1|1)+NUM,0);
    }
    
    inline void add(int k,int l,int r,int xl,int xr,int from,int w,int opt){
        if(xl<=l&&r<=xr){
            if(opt==2)add(from,k+NUM,w);
            else if(opt==3)add(k,from,w);
            return;
        }
        int mid=(l+r)>>1;
        if(xl<=mid)add(k<<1,l,mid,xl,xr,from,w,opt);
        if(xr>=mid+1)add(k<<1|1,mid+1,r,xl,xr,from,w,opt);
    }
    
    priority_queue<node> q;
    
    inline void dijkstra(){
        s=pos[s];
        q.push((node){0,s});
        dis[s]=0;
        while(!q.empty()){
            int x=q.top().u;
            q.pop();
            if(vis[x])continue;
            vis[x]=1;
            for(int i=head[x];i!=-1;i=e[i].next){
                int y=e[i].v;
                if(!vis[y]&&dis[y]>dis[x]+e[i].w){
                    dis[y]=dis[x]+e[i].w;
                    q.push((node){dis[y],y});//想不到吧，这一行打错使我调了半个小时 
                }
            }
        }
        s<<=1;
        if(s>=1)dijkstra();
    }
    
    signed main(){
        memset(head,-1,sizeof(head));
        memset(dis,127,sizeof(dis));
        memset(vis,0,sizeof(vis));
        input(n);input(m);input(s);
        build(1,1,n);
        for(int i=1;i<=m;i++){
            int opt;
            input(opt);
            if(opt==1){
                int u,v,w;
                input(u);input(v);input(w);
                add(pos[u],pos[v],w);
            }
            else if(opt==2){
                int u,l,r,w;
                input(u);input(l);input(r);input(w);
                add(1,1,n,l,r,pos[u],w,opt);
            }
            else if(opt==3){
                int u,l,r,w;
                input(u);input(l);input(r);input(w);
                add(1,1,n,l,r,pos[u],w,opt);
            }
        }
        dijkstra();
    //  for(int i=1;i<=4*n;i++)cout<<i<<' '<<dis[i]<<endl;
        for(int i=1;i<=n;i++)output(dis[pos[i]]<=1e15?dis[pos[i]]:-1),putchar(' ');
    }

转载于:https://www.cnblogs.com/Y15BeTa/p/11318060.html