給一張圖，每次操作或詢問所有u到v路徑上邊權最大值的最小值，或刪除一條邊
離線，反過來操作，刪邊變成加邊，用LCT維護圖的聯通就行。
#include <cstdio>#include <iostream>#include <algorithm>#include <map>#include <iostream>#define N 1000010using namespace std;typedef pair<int,int> PRs;int n,m,q,tp,cnt;int f[N],ch[N][2],w[N],v[N],sta[N],Ans[N],p[N];bool rev[N];struct edge{ int u,v,w,g; friend bool Operator <(edge a,edge b){ return a.w<b.w; }}E[N];struct stp{ int k,u,v;}s[N];map<prs,int> umap;inline void reaD(int &x){ char Ch=getchar();x=0; for(;Ch>'9'||Ch<'0';Ch=getchar()); for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=getchar());}inline int isl(int x){return ch[f[x]][1]==x;}inline int isr(int x){return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;}inline void pushdown(int x){ if(!(x&&rev[x]))return; swap(ch[x][0],ch[x][1]); if(ch[x][0]) rev[ch[x][0]]^=1; if(ch[x][1]) rev[ch[x][1]]^=1; rev[x]=0;}inline void upd(int x){ if(!x) return; w[x]=x; if(ch[x][0]&&v[w[ch[x][0]]]>v[w[x]]) w[x]=w[ch[x][0]]; if(ch[x][1]&&v[w[ch[x][1]]]>v[w[x]]) w[x]=w[ch[x][1]];}inline void rot(int x){ int y=f[x],z=f[y],lor=isl(x); if(!isr(y)) ch[z][ch[z][1]==y]=x;f[x]=z; if(ch[y][lor]=ch[x][lor^1]) f[ch[y][lor]]=y; f[ch[x][lor^1]=y]=x;upd(y);upd(x);}inline void splay(int x){ sta[tp=1]=x; for(int i=x;!isr(i);i=f[i]) sta[++tp]=f[i]; for(;tp;tp--) pushdown(sta[tp]); for(;!isr(x);rot(x))if(!isr(f[x]))rot(isl(x)^isl(f[x])?x:f[x]);}inline void access(int x){int t=0;for(;x;t=x,x=f[x])splay(x),ch[x][1]=t,upd(x);}inline void reverse(int x){access(x);splay(x);rev[x]^=1;}inline void link(int x,int y){reverse(x);f[x]=y;splay(x);}inline void cut(int x,int y){reverse(x);access(y);splay(y);ch[y][0]=f[x]=0;}inline int query(int x,int y){reverse(x);access(y);splay(y);return w[y];}int fa[N];int fifa(int x){return fa[x]==x?x:fa[x]=fifa(fa[x]);}inline void kru(){ sort(E+1,E+1+m);int tt=0; for(int i=1;i<=n;i++) fa[i]=i;cnt=n; for(int i=1;i<=m;i++) E[i].g=i; for(int i=1;i<=m;i++){ if(umap[prs(E[i].u,E[i].v)]) {umap[prs(E[i].u,E[i].v)]=E[i].g;continue;} int x=fifa(E[i].u),y=fifa(E[i].v); if(x==y) continue; v[++cnt]=E[i].w,link(E[i].u,cnt),link(E[i].v,cnt),fa[x]=y,p[cnt]=i; }}int main(){ reaD(n);reaD(m);reaD(q); for(int i=1;i<=m;i++){ reaD(E[i].u),reaD(E[i].v),reaD(E[i].w); if(E[i].u>E[i].v) swap(E[i].u,E[i].v); } for(int i=1;i<=q;i++){ reaD(s[i].k);reaD(s[i].u);reaD(s[i].v); if(s[i].u>s[i].v) swap(s[i].u,s[i].v); if(s[i].k==2) umap[prs(s[i].u,s[i].v)]=1; } kru(); for(int i=q;i;i--) if(s[i].k==1) Ans[i]=v[query(s[i].u,s[i].v)]; else{ int k=query(s[i].u,s[i].v),x=umap[prs(s[i].u,s[i].v)]; if(v[k]<E[x].w) continue; cut(E[p[k]].u,k);cut(E[p[k]].v,k); p[++cnt]=x;v[cnt]=E[p[cnt]].w; link(s[i].u,cnt);link(s[i].v,cnt); } for(int i=1;i<=q;i++) if(s[i].k==1) printf("%d/n",Ans[i]);}新聞熱點
疑難解答
