題意：一個無向連通圖，點有點權，支持單點修改和查詢，查詢$(x,y)$是找出一條$x$到$y$的簡單路徑使得路徑點權最小值最小，輸出這個最小值

碼農題...而且細節很多...

先找邊雙連通分量縮點，對于每個邊雙，新建一個節點和邊雙中的每個點連邊，不屬于任何邊雙的邊就直接連，這樣可以建出一棵樹，然后就變成樹上的問題了，因為進入一個邊雙就可以遍歷它的所有點

對于新建的點，開一個multiset存它兒子的權值，它自己的權值設為multiset的最小值

查詢就是路徑$\min$，注意如果lca是新建點，那么這個lca的父親的權值也應該被統計

修改就修改單點，如果父親是新建點就更新它的multiset還有權值

注意在tarjan時棧中保存的應該是邊而不是點

#include<stdio.h> #include<vector> #include<set> using namespace std; const int inf=2147483647; int v[100010],n,m,q,C; struct tree{int h[200010],nex[400010],to[400010],M;multiset<int>s[200010];void ins(int a,int b){M++;to[M]=b;nex[M]=h[a];h[a]=M;}void add(int a,int b){ins(a,b);ins(b,a);}int fa[200010][18],dep[200010];void dfs(int x){dep[x]=dep[fa[x][0]]+1;for(int i=h[x];i;i=nex[i]){if(to[i]!=fa[x][0]){if(x>n)s[x].insert(v[to[i]]);fa[to[i]][0]=x;dfs(to[i]);}}if(x>n)v[x]=*s[x].begin();}int lca(int x,int y){int i;if(dep[x]<dep[y])swap(x,y);for(i=17;i>=0;i--){if(dep[fa[x][i]]>=dep[y])x=fa[x][i];}if(x==y)return x;for(i=17;i>=0;i--){if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}}return fa[x][0];}int siz[200010],son[200010],pos[200010],bl[200010];void dfs1(int x){int i,k=0;siz[x]=1;for(i=h[x];i;i=nex[i]){if(to[i]!=fa[x][0]){dfs1(to[i]);siz[x]+=siz[to[i]];if(siz[to[i]]>siz[k])k=to[i];}}son[x]=k;}void dfs2(int x,int chain){pos[x]=++M;bl[x]=chain;if(son[x])dfs2(son[x],chain);for(int i=h[x];i;i=nex[i]){if(to[i]!=fa[x][0]&&to[i]!=son[x])dfs2(to[i],to[i]);}}int T[800010];void modify(int x,int v){T[x+=M]=v;for(x>>=1;x;x>>=1)T[x]=min(T[x<<1],T[x<<1|1]);}int query(int s,int t){int res=inf;for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){if(~s&1)res=min(res,T[s^1]);if(t&1)res=min(res,T[t^1]);}return res;}void gao(){int i,j;dfs(1);for(j=1;j<18;j++){for(i=1;i<=C;i++)fa[i][j]=fa[fa[i][j-1]][j-1];}dfs1(1);M=0;dfs2(1,1);for(M=1;M<=C+1;M<<=1);for(i=0;i<M;i++)T[i+M]=inf;for(i=1;i<=C;i++)T[pos[i]+M]=v[i];for(i=M-1;i>0;i--)T[i]=min(T[i<<1],T[i<<1|1]);}int querych(int x,int y){int res=inf;while(bl[x]!=bl[y]){if(dep[bl[x]]<dep[bl[y]])swap(x,y);res=min(res,query(pos[bl[x]],pos[x]));x=fa[bl[x]][0];}if(pos[x]>pos[y])swap(x,y);res=min(res,query(pos[x],pos[y]));if(x>n)res=min(res,v[fa[x][0]]);return res;}void modifypt(int x,int d){if(fa[x][0]&&fa[x][0]>n){s[fa[x][0]].erase(s[fa[x][0]].find(v[x]));s[fa[x][0]].insert(d);modify(pos[fa[x][0]],*s[fa[x][0]].begin());}v[x]=d;modify(pos[x],d);} }tr; struct graph{int h[100010],nex[200010],to[200010],M;graph(){M=1;}int fix(int i){return i&1?i^1:i;}void add(int a,int b){M++;to[M]=b;nex[M]=h[a];h[a]=M;}int dfn[100010],low[100010],stk[100010],vis[100010],tp,K;bool ins[200010];vector<int>V;void dfs(int x){int i,j,t,n,m;dfn[x]=low[x]=++M;for(i=h[x];i;i=nex[i]){if(!dfn[to[i]]){ins[stk[++tp]=fix(i)]=1;dfs(to[i]);low[x]=min(low[x],low[to[i]]);if(low[to[i]]>=dfn[x]){K++;V.clear();j=tp;m=0;do{t=stk[j--];m++;if(vis[to[t]]!=K){vis[to[t]]=K;V.push_back(to[t]);}if(vis[to[t^1]]!=K){vis[to[t^1]]=K;V.push_back(to[t^1]);}}while(t!=fix(i));n=V.size();if(m<n)tr.add(x,to[i]);else{C++;for(int x:V)tr.add(x,C);}do{ins[t=stk[tp--]]=0;}while(t!=fix(i));}}else{low[x]=min(low[x],dfn[to[i]]);if(!ins[fix(i)]&&dfn[to[i]]<dfn[x])ins[stk[++tp]=fix(i)]=1;}}}void gao(){int i,x,y;for(i=1;i<=n;i++)scanf("%d",v+i);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}M=0;C=n;dfs(1);} }g; int main(){char s[5];int x,y;scanf("%d%d%d",&n,&m,&q);g.gao();tr.gao();while(q--){scanf("%s%d%d",s,&x,&y);if(s[0]=='C')tr.modifypt(x,y);elseprintf("%d\n",tr.querych(x,y));} }

轉載于:https://www.cnblogs.com/jefflyy/p/9480473.html

總結

以上是生活随笔為你收集整理的[CF487E]Tourists的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。