• uoj #274. 【清华集训2016】温暖会指引我们前行 LCT维护边权 + 动态维护最小生成树


    题面:http://uoj.ac/problem/274

    动态维护一下最小生成树即可. 

    #include<bits/stdc++.h> 
    #define ll long long 
    #define maxn 1000000 
    #define inf 1000000000000 
    using namespace std;
     
    void setIO(string s)
    {
        string in=s+".in",out=s+".out"; 
        freopen(in.c_str(),"r",stdin); 
      //   freopen(out.c_str(),"w",stdout); 
    } 
    struct Union
    {
        int p[maxn]; 
        void init()
        {
            for(int i=0;i<maxn;++i) p[i]=i; 
        }
        int find(int x)
        {
            return p[x]==x?x:p[x]=find(p[x]); 
        }
        void merge(int a,int b)
        {
            int x=find(a),y=find(b);
            if(x==y) return ; 
            p[x]=y;  
        }
    }ut; 
    struct LCT
    {
        #define lson ch[x][0]
        #define rson ch[x][1] 
        int f[maxn],ch[maxn][2],sta[maxn],rev[maxn];  
        ll w[maxn],val[maxn],sumv[maxn],minv[maxn]; 
    
        int isRoot(int x)
        {
            return !(ch[f[x]][0]==x||ch[f[x]][1]==x); 
        }
        int get(int x)
        {
            return ch[f[x]][1]==x; 
        }
        void pushdown(int x)
        {
            if(!x||!rev[x]) return;
            mark(lson), mark(rson),rev[x]^=1; 
        }
        void mark(int x)
        {
            if(!x) return;
            swap(lson,rson),rev[x]^=1; 
        }
        void pushup(int x)
        {
            if(!x) return; 
            sumv[x]=sumv[lson]+sumv[rson]+val[x];   
            minv[x]=min(min(minv[lson],minv[rson]),w[x]); 
        }
        void rotate(int x)
        {
            int old = f[x], fold = f[old], which = get(x); 
            if(!isRoot(old)) ch[fold][ch[fold][1] == old] = x; 
            ch[old][which] = ch[x][which ^ 1], f[ch[old][which]] = old; 
            ch[x][which ^ 1] = old, f[old] = x, f[x] = fold; 
            pushup(old), pushup(x); 
        }
        void splay(int x)
        {
            int u=x,v=0,fa; 
            sta[++v]=u; 
            while(!isRoot(u)) sta[++v]=f[u],u=f[u]; 
            while(v) pushdown(sta[v--]); 
            for(u=f[u];(fa=f[x])!=u;rotate(x)) 
                if(f[fa]!=u) 
                    rotate(get(fa)==get(x)?fa:x); 
        }     
        void Access(int x)
        {
            int t=0;
            while(x) splay(x),rson=t,pushup(x),t=x,x=f[x]; 
        }
        void MakeRoot(int x)
        {
            Access(x),splay(x), mark(x); 
        }
        void link(int a,int b)
        {
            MakeRoot(a),f[a]=b; 
        }
        int FindRoot(int x)
        {
            Access(x), splay(x);
            while(lson) x=lson; 
            return x;  
        } 
        void split(int x,int y)
        {
            MakeRoot(x), Access(y), splay(y); 
        }
        void cut(int a,int b)
        {
            split(a,b),ch[b][0]=f[a]=0, pushup(b); 
        }      
        int find(int x)
        {
            if(w[x]==minv[x]) return x; 
            return minv[lson]==minv[x]?find(lson):find(rson); 
        }
    }tree;  
    int h1[maxn],h2[maxn]; 
    char opt[20]; 
    #define idx(i) (i+n) 
     
    int main()
    {
       //  setIO("input");
        ll t; 
        int n,m,id,u,v,l,cur; 
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;++i) tree.w[i]=inf; 
        tree.minv[0]=inf;  
        ut.init();    
        while(m--)
        {
            scanf("%s",opt); 
            switch(opt[0])  
            {
                case 'f' : 
                { 
                    scanf("%d%d%d%lld%d",&id,&u,&v,&t,&l); 
                    ++id,++u,++v; 
                    h1[cur=idx(id)]=u,h2[idx(id)]=v; 
                    if(ut.find(u)!=ut.find(v)) 
                    {
                        ut.merge(u,v); 
                        tree.val[cur]=l,tree.w[cur]=t;   
                        ut.merge(u,cur),ut.merge(v,cur);  
                        tree.link(u,cur), tree.link(v,cur);          
                    }  
                    else
                    {  
                        tree.split(u,v);     
                        if(tree.minv[v] < t) 
                        { 
                            int k=tree.find(v);       
                            tree.cut(k, h1[k]), tree.cut(k, h2[k]);  
                            tree.val[cur=idx(id)]=l,tree.w[cur]=t;    
                            ut.merge(u,cur), ut.merge(v,cur);          
                            tree.link(u,cur),tree.link(v,cur); 
                        }       
                    }
                    break; 
                }
                case 'm' : 
                {  
                    scanf("%d%d",&u,&v); 
                    ++u,++v; 
                    if(ut.find(u)!=ut.find(v))  
                    {
                        printf("-1
    "); 
                    }
                    else
                    {
                        tree.split(u,v), printf("%lld
    ",tree.sumv[v]); 
                    }
                    break; 
                }
                case 'c' : 
                {
                    scanf("%d%d",&id,&l); 
                    ++id;      
                    tree.Access(cur=idx(id)),tree.val[cur]=l,tree.pushup(cur); 
                    break; 
                }
            }
        }
        return 0; 
    }
    

      

  • 相关阅读:
    github高效搜索使用总结
    使用redis防止商品超发
    yield对性能提升的一次小小测试
    实例直观解释sessionid的作用
    phper必知必会(二)
    phper必知必会(一)
    搭建laravel/homestead虚拟化开发环境
    【博客主题】自用主题备份 (SimpleMemory DIY)
    CentOS 7 配置清华大学EPEL镜像
    CentOS7网络配置-解决虚拟机更改网卡IP不生效问题
  • 原文地址:https://www.cnblogs.com/guangheli/p/10999799.html
一二三 - 开发者的网上家园