【CodeForces 487E】Tourists / 题解

题目描述

求简单无向图两点路径上最小权值，支持修改。

思路

先把图中的点双缩点，维护圆方树，把方点的值设为它儿子中点权最小的点的点权，树链剖分。利用 Multiset 维护每个点双的信息即可。

代码

#include 
#define ls (p<<1) 100010 #define rs (p<<1|1) maxn mid ((l+r)>>1)
#define ll long long
#define inf INT_MAX
using namespace std;
int n,m,q,val[maxn<<2],pointsum; multisetst[maxn<<2]; struct ios{ inline char read(){ static const int in_len="1<<18|1;" buf[in_len],*s,*t; return (s="=t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;" } template  inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
};
struct Graph{
    Edge l[maxn<<2]; int head[maxn<<1],cnt,ind; fa[maxn<<1],son[maxn<<1]; top[maxn<<1],dep[maxn<<1]; siz[maxn<<1],id[maxn<<1]; rid[maxn<<1]; void add(int a,int b){ l[++cnt]="Edge(b,head[a]);head[a]=cnt;" } pre_work(int u,int f){ fa[u]="f,siz[u]=1,dep[u]=dep[f]+1;" maxson="-1;" for (int i="head[u];i;i=l[i].next){" v="l[i].to;" if (v="=f)" continue; pre_work(v,u); siz[u]+="siz[v];" (siz[v]>maxson)
                maxson=siz[v],son[u]=v;
        }
    }
    void Re_Build(int u,int topf){
        top[u]=topf;rid[id[u]=++ind]=u;
        if (son[u]) Re_Build(son[u],topf);
        for (int i=head[u];i;i=l[i].next){
            int v=l[i].to;
            if (v==fa[u]||v==son[u]) continue;
            Re_Build(v,v);
        }
    }
    int tree[maxn<<4]; void pushup(int p){ tree[p]="min(tree[ls],tree[rs]);" } build(int l,int r,int if (l="=r){tree[p]=val[rid[l]];return;}" build(l,mid,ls),build(mid+1,r,rs); pushup(p); update(int t,int v,int (t<="mid)" update(l,mid,t,v,ls); else update(mid+1,r,t,v,rs); int query(int>R||r=L&&r<=r) return tree[p]; min(query(l,mid,l,r,ls),query(mid+1,r,l,r,rs)); } int path_query(int x,int y){ res="inf;" while(top[x]!="top[y]){" if (dep[top[x]]dep[y]) swap(x,y);
        res=min(res,Query(1,pointsum,id[x],id[y],1));
        if (x>n) res=min(res,val[fa[x]]);
        return res;
    }
}G;
struct DAG{
    Edge l[maxn<<1]; int head[maxn],cnt; dfn[maxn],low[maxn]; sta[maxn],ind,top; void add(int a,int b){ l[++cnt]="Edge(b,head[a]);" head[a]="cnt;" } tarjan(int u){ low[u]="dfn[u]=++ind;" sta[++top]="u;" for (int i="head[u];i;i=l[i].next){" v="l[i].to;" if (!dfn[v]){ tarjan(v); (low[v]>=dfn[u]){
                    int j=-1;pointsum++;
                    while(j!=v){
                        j=sta[top--];
                        G.Add(j,pointsum);
                    }
                    G.Add(u,pointsum);
                }
            }
            else low[u]=min(low[u],dfn[v]);
        }
    }
}D;
int main(){
    scanf("%d%d%d",&n,&m,&q);
    pointsum=n;
    for (int i=1;i<=n;i++) scanf("%d",val+i); for (int i="1,x,y;i<=m;i++){" scanf("%d%d",&x,&y); d.add(x,y),d.add(y,x); } if (!d.dfn[i]) d.tarjan(i); g.pre_work(1,0),g.re_build(1,1); st[g.fa[i]-n].insert(val[i]); val[i]="st[i-n].empty()?inf:*st[i-n].begin();" g.build(1,pointsum,1); char op[2]; scanf("%s%d%d",op,&x,&y); (op[0]="='C'){" g.update(1,pointsum,g.id[x],y,1); (x="=1)" {val[x]="y;continue;}" int t="G.fa[x];" st[t-n].erase(st[t-n].find(val[x])); st[t-n].insert(y); mt="*st[t-n].begin();" (mt="=val[t])" g.update(1,pointsum,g.id[t],mt,1); val[t]="mt;val[x]=y;" printf("%d\n",g.path_query(x,y)); return 0; }< pre>