必威官网沉迷Link-Cut tree无法自拔之:[BZOJ3669][Noi2014] 魔法森林。沉迷Link-Cut tree无法自拔之:[BZOJ2594][Wc2006]水管局长数据增长版本。

发源蒟蒻 \(Hero \_of \_Someone\)
的 \(LCT\) 学习笔记
$
$
起一个十分好之做法是 \(spfa\)
,但是咱无聊 \(spfa\) , 来聊 \(LCT\)
\(LCT\) 做法跟 \(spfa\) 的做法实际上有接触像,
预先拿具备的边按 \(a\) 的价值由小至大排,
再坐 \(b\)
的值吗边权来动态的保安最小生成树,
答案就是为 眼下安插边的 \(a\)
值加上最小生成树中之太要命边权
的极其小值
$
$
此外, 用 \(LCT\) 维护 \(MST\) ,
就是于添边的早晚要遇上环且环上极丰富之边边权大于当前限, 就以最可怜边 \(cut\) , 再将手上边添入

根源蒟蒻 \(Hero \_of \_Someone\)
的 \(LCT\) 学习笔记
$
$
顿时该算是道套路题吧, 如果将图备受的界限换成点, 再以边权变点权, 就足以用
\(LCT\) 来维护了
就道题之中坚做法尽管是, 用 \(LCT\)
来动态地维护最小生成树,
万一如此做吧, 题目中要求的删边操作就未极端好将,
不过既然只有删边操作的话, 我们尽管可考虑离线处理,
以非会见于剔除的边先加进图备受飞 \(Kruskal\) , 然后化删边为添边,
倒着来处理各一样组询问.
$
$
此外, 用 \(LCT\) 维护 \(MST\) ,
就是在添边的时段要碰到环且环上极度丰富之边边权大于当前边, 就以最老边 \(cut\) , 再将手上止添入

//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define N (50040)
#define M (100010)
#define RG register
using namespace std;
inline int gi(){ RG int x=0,q=1; RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') q=-1,ch=getchar(); while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=getchar(); return q*x; }
void File(){freopen(".in","r",stdin);freopen(".out","w",stdout);}

int n,m;
struct Edge{ 
  int u,v,a,b; 
  bool operator<(const Edge& x)const{ return a<x.a; }
}e[M];

inline void init(){
  n=gi(),m=gi();
  for(RG int i=1;i<=m;i++){
    e[i].u=gi(),e[i].v=gi();
    e[i].a=gi(),e[i].b=gi();
  }
  sort(e+1,e+m+1);
}

int Max[N+M],val[N+M];
int ch[N+M][2],fa[N+M],rev[N+M];

inline void cur(int x,int y){ val[x]=Max[x]=y; }

inline bool cnm(int x,int y){ return e[x].b<e[y].b; }

inline void up(int x){
  Max[x]=max(Max[ch[x][0]],Max[ch[x][1]],cnm);
  Max[x]=max(Max[x],val[x],cnm);
}

inline void reverse(int x){
  swap(ch[x][0],ch[x][1]);
  rev[x]^=1;
}

inline void down(int x){
  if(!rev[x]) return ;
  reverse(ch[x][0]);
  reverse(ch[x][1]);
  rev[x]=0;
}

inline bool is_root(int x){ return ch[fa[x]][0]!=x && x!=ch[fa[x]][1]; }

inline bool lr(int x){ return x==ch[fa[x]][1]; }

inline void rotate(int x){
  RG int y=fa[x],z=fa[y],k=lr(x);
  if(!is_root(y)) ch[z][lr(y)]=x;
  fa[x]=z; fa[ch[x][k^1]]=y; fa[y]=x;
  ch[y][k]=ch[x][k^1]; ch[x][k^1]=y;
  up(y); up(x);
}

int st[N+M];
inline void splay(int x){
  RG int y=x,top=0;
  while(1){
    st[++top]=y;
    if(is_root(y)) break;
    y=fa[y];
  }
  for(RG int i=top;i;i--) down(st[i]);
  while(!is_root(x)){
    if(!is_root(fa[x])) rotate(lr(x)^lr(fa[x])?x:fa[x]);
    rotate(x);
  }
}

inline void access(int x){
  RG int y=0;
  while(x){ splay(x);
    ch[x][1]=y; fa[y]=x;
    up(x); y=x; x=fa[x];
  }
}

inline void make_root(int x){
  access(x); splay(x); reverse(x);
}

inline int find(int x){
  while(fa[x]) x=fa[x];
  return x;
}

inline void link(int x,int y){
  if(find(x)==find(y)) return ;
  make_root(x); fa[x]=y;
}

inline void cut(int x,int y){
  make_root(x); access(y); splay(y);
  if(ch[y][0]==x) ch[y][0]=0,fa[x]=0,up(y);
}

inline int query(int x,int y){
  make_root(x); access(y); splay(y);
  return Max[y];
}

inline void Insert(int id){
  RG int x=e[id].u,y=e[id].v;
  if(x==y) return ;
  if(find(x)==find(y)){
    RG int tmp=query(x,y);
    if(e[tmp].b<=e[id].b) return ;
    cut(n+tmp,e[tmp].u);
    cut(n+tmp,e[tmp].v);
  }
  cur(n+id,id);
  link(x,n+id);
  link(y,n+id);
}

inline void work(){
  RG int ans=1<<30;
  for(RG int i=1;i<=m;i++){ 
    Insert(i);
    if(find(1)!=find(n)) continue;
    ans=min(ans,e[i].a+e[query(1,n)].b);
  }
  if(ans==1<<30) ans=-1;
  printf("%d\n",ans);
}

int main(){ init(); work(); return 0; }
//made by Hero_of_Someone
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define N (100010)
#define M (1000010)
#define RG register
using namespace std;
inline int gi(){ RG int x=0; RG char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar();
  while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x; }

int n,m,q;
struct Edge{ 
  int u,v,w; 
  bool operator<(const Edge&a)const{ 
    return u==a.u?v<a.v:u<a.u; 
  }
  bool operator<(const pair<int,int>& a)const{
    return u==a.first?v<a.second:u<a.first;
  }
}e[M];

struct Que{ int op,x,y; }Q[N];

//-----------------------------------------------------------
int Fa[N];
inline int Find(RG int x){ return Fa[x]==x?x:Fa[x]=Find(Fa[x]); }

struct EEE{
  int u,v,w,id;
  bool operator<(const EEE& a)const{ return w<a.w; }
  void operator=(const Edge& a){
    u=a.u,v=a.v,w=a.w,id=(&a)-e;
  }
}E[M];

int num,head[N],nxt[N<<1],to[N<<1],w[N<<1]; //w为该边原来的编号
inline void add(int u,int v,int d){
  nxt[++num]=head[u];to[num]=v;w[num]=d;head[u]=num;
  nxt[++num]=head[v];to[num]=u;w[num]=d;head[v]=num;
}

bool v[M];
inline void kruskal(){
  RG int top=0;
  for(RG int i=1;i<=n;i++) Fa[i]=i;
  for(RG int i=1;i<=m;i++){
    if(v[i]) continue;
    E[++top]=e[i];
  }
  sort(E+1,E+top+1);
  for(RG int i=1;i<=top;i++){
    RG int x=E[i].u,y=E[i].v;
    RG int fx=Find(x),fy=Find(y);
    if(fx==fy) continue;
    Fa[fx]=fy; add(x,y,E[i].id);
  }
}

inline void init(){
  n=gi(),m=gi(),q=gi();
  for(RG int i=1;i<=m;i++){
    e[i].u=gi(),e[i].v=gi(),e[i].w=gi();
  }
  sort(e+1,e+m+1);
  for(RG int i=1;i<=q;i++){
    Q[i].op=gi(),Q[i].x=gi(),Q[i].y=gi();
    if(Q[i].op==2){
      RG int V=lower_bound(e+1,e+m+1,make_pair(Q[i].x,Q[i].y))-e;
      Q[i].x=V; v[V]=1;
    }
  }q++;
  kruskal();
}
//---------------------------------------------------------------

int val[N+M],Max[N+M];
int ch[N+M][2],fa[N+M],rev[N+M];

inline void cur(int x,int y){ val[x]=Max[x]=y; }

int vis[N];
inline void dfs(RG int x,RG int f,RG int d){
  if(vis[x]) return ;
  vis[x]=1; cur(x,0);
  if(f){ cur(n+d,d); fa[n+d]=f; fa[x]=n+d; } //将边转换成点插入树中
  for(RG int i=head[x];i;i=nxt[i])
    dfs(to[i],x,w[i]);
}

inline bool cnm(int x,int y){ return e[x].w<e[y].w; }
inline void up(int x){
  Max[x]=max(Max[ch[x][0]],Max[ch[x][1]],cnm);
  Max[x]=max(Max[x],val[x],cnm);
}

inline void reverse(int x){
  swap(ch[x][0],ch[x][1]);
  rev[x]^=1;
}

inline void down(int x){
  if(!rev[x]) return ;
  reverse(ch[x][0]);
  reverse(ch[x][1]);
  rev[x]=0;
}

inline bool is_root(int x){ return ch[fa[x]][0]!=x && x!=ch[fa[x]][1]; }

inline bool lr(int x){ return x==ch[fa[x]][1]; }

inline void rotate(int x){
  RG int y=fa[x],z=fa[y],k=lr(x);
  if(!is_root(y)) ch[z][lr(y)]=x;
  fa[x]=z; fa[ch[x][k^1]]=y; fa[y]=x;
  ch[y][k]=ch[x][k^1]; ch[x][k^1]=y;
  up(y); up(x);
}

int st[N+M];
inline void splay(int x){
  RG int y=x,top=0;
  while(1){
    st[++top]=y;
    if(is_root(y)) break;
    y=fa[y];
  }
  for(RG int i=top;i;i--) down(st[i]);
  while(!is_root(x)){
    if(!is_root(fa[x])) rotate(lr(x)^lr(fa[x])?x:fa[x]);
    rotate(x);
  }
}

inline void access(int x){
  RG int y=0;
  while(x){ splay(x);
    ch[x][1]=y; fa[y]=x;
    up(x); y=x; x=fa[x];
  }
}

inline void make_root(int x){
  access(x); splay(x); reverse(x);
}

inline int query(int x,int y){
  make_root(x); access(y); splay(y);
  return Max[y];
}

inline int find(int x){
  while(fa[x]) x=fa[x];
  return x;
}

inline void link(int x,int y){
  if(find(x)==find(y)) return ;
  make_root(x); fa[x]=y;
}

inline void cut(int x,int y){
  make_root(x); access(y); splay(y);
  if(ch[y][0]==x) ch[y][0]=0,fa[x]=0,up(y);
}

inline void Insert(int id){
  RG int x=e[id].u,y=e[id].v;
  if(find(x)==find(y)){
    RG int tmp=query(x,y);
    if(e[tmp].w<=e[id].w) return ;
    cut(n+tmp,e[tmp].u);
    cut(n+tmp,e[tmp].v);
  }
  cur(n+id,id);
  link(x,n+id);
  link(y,n+id);
}

int Ans[N],top;
inline void work(){
  for(RG int i=1;i<=n;i++) dfs(i,0,0);
  while(--q){
    if(Q[q].op==2) Insert(Q[q].x);
    else Ans[++top]=e[query(Q[q].x,Q[q].y)].w;
  }
  for(RG int i=top;i;i--) printf("%d\n",Ans[i]);
}

int main(){ init(); work(); return 0; }

相关文章