时间戳

首页 > 技术文章 > Link-Cut-Tree 题目总结

Link-Cut-Tree 题目总结

bxd123 2019-10-06 12:16 原文

P3690 【模板】Link Cut Tree （动态树）

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
const int N=2e6+10;
int fa[N],val[N],sum[N],son[N][2],rev[N],st[N];
int get(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void up(int x){sum[x]=sum[son[x][1]]^sum[son[x][0]]^val[x];}
void change(int x){swap(son[x][0],son[x][1]);rev[x]^=1;}
void down(int x)
{   
    if(!rev[x])return ;
    rev[x]=0;
    if(son[x][0])change(son[x][0]);
    if(son[x][1])change(son[x][1]);
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=son[fa[x]][1]==x,w=son[x][k^1];
    if(get(y))son[z][son[z][1]==y]=x;son[x][k^1]=y;son[y][k]=w;
    if(w)fa[w]=y;fa[y]=x;fa[x]=z;
    up(y);up(x);
}
void splay(int x)
{
    int y=x,top=0;st[++top]=y;
    while(get(y))st[++top]=y=fa[y];
    while(top)down(st[top--]);
    while(get(x))
    {
        int y=fa[x],z=fa[y];
        if(get(y))
        rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
        rotate(x);
    }up(x);
}
void access(int x)
{   
    for(int y=0;x;x=fa[y=x])
    splay(x),son[x][1]=y,up(x);
}
void makeroot(int x)
{
    access(x);splay(x);change(x);
}
int findroot(int x)
{
    access(x);splay(x);
    while(son[x][0])down(x),x=son[x][0];
    splay(x);return x;
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
    makeroot(x);if(findroot(y)!=x)fa[x]=y;
}
void cut(int x,int y)
{
    split(x,y);
    if(findroot(y)==x&&fa[y]==x&&!son[y][0])
    fa[y]=son[x][1]=0,up(x);
}int n,m,x,y,op;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    while(m--)
    {
        scanf("%d%d%d",&op,&x,&y);
        if(op==0)split(x,y),printf("%d\n",sum[y]);
        if(op==1)link(x,y);
        if(op==2)cut(x,y);
        if(op==3)splay(x),val[x]=y;//这里不up也没事 反正问的时候也会up
    }
    return 0;
}
View Code

 

 

维护联通：

 

P2147 [SDOI2008]洞穴勘测

题意： 就是可删除的并查集

题解： 没啥好说的 比模板简单

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
////////////////////////////////////
const int N=2e6+10;
int fa[N],son[N][2],rev[N],st[N];
int get(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void change(int x){swap(son[x][1],son[x][0]);rev[x]^=1;}
void down(int x)
{
    if(!rev[x])return ;
    rev[x]=0;
    if(son[x][1])change(son[x][1]);
    if(son[x][0])change(son[x][0]);
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=son[fa[x]][1]==x,w=son[x][k^1];
    if(get(y))son[z][son[z][1]==y]=x;son[x][k^1]=y;son[y][k]=w;
    if(w)fa[w]=y;fa[y]=x;fa[x]=z;
}
void splay(int x)
{   
    int y=x,top=0;st[++top]=y;
    while(get(y))st[++top]=y=fa[y];
    while(top)down(st[top--]);

    while(get(x))
    {
        int y=fa[x],z=fa[y];
        if(get(y))
        rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
        rotate(x);
    }
}
void access(int x)
{
    for(int y=0;x;x=fa[y=x])
    splay(x),son[x][1]=y;
}
void makeroot(int x)
{
    access(x);splay(x);change(x);
}
int findroot(int x)
{
    access(x);splay(x);
    while(son[x][0])down(x),x=son[x][0];
    splay(x);return x;
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
    makeroot(x);
    if(findroot(y)!=x)fa[x]=y;
}
bool judge(int x,int y)
{
    makeroot(x);
    return findroot(y)==x;
}
void cut(int x,int y)
{
    split(x,y); 
    if(findroot(y)==x&&fa[y]==x&&!son[y][0])
    fa[y]=son[x][1]=0;
}char s[100];int n,m,x,y;
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%s %d%d",s,&x,&y);
        if(s[0]=='Q')printf("%s\n",judge(x,y)?"Yes":"No");
        if(s[0]=='C')link(x,y);
        if(s[0]=='D')cut(x,y);
    }
    return 0;
}
View Code

 

P3950 部落冲突 

题解： 最无脑的lct  和上面那题有得一拼 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
////////////////////////////////////
const int N=2e6+10;
int fa[N],son[N][2],rev[N],st[N];
int get(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void change(int x){swap(son[x][1],son[x][0]);rev[x]^=1;}
void down(int x)
{
    if(!rev[x])return ;
    rev[x]=0;
    if(son[x][1])change(son[x][1]);
    if(son[x][0])change(son[x][0]);
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=son[fa[x]][1]==x,w=son[x][k^1];
    if(get(y))son[z][son[z][1]==y]=x;son[x][k^1]=y;son[y][k]=w;
    if(w)fa[w]=y;fa[y]=x;fa[x]=z;
}
void splay(int x)
{   
    int y=x,top=0;st[++top]=y;
    while(get(y))st[++top]=y=fa[y];
    while(top)down(st[top--]);

    while(get(x))
    {
        int y=fa[x],z=fa[y];
        if(get(y))
        rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
        rotate(x);
    }
}
void access(int x)
{
    for(int y=0;x;x=fa[y=x])
    splay(x),son[x][1]=y;
}
void makeroot(int x)
{
    access(x);splay(x);change(x);
}
int findroot(int x)
{
    access(x);splay(x);
    while(son[x][0])down(x),x=son[x][0];
    splay(x);return x;
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
    makeroot(x);
    if(findroot(y)!=x)fa[x]=y;
}
bool judge(int x,int y)
{
    makeroot(x);
    return findroot(y)==x;
}
void cut(int x,int y)
{
    split(x,y); 
    if(findroot(y)==x&&fa[y]==x&&!son[y][0])
    fa[y]=son[x][1]=0;
}char s[100];int n,m,x,y;
int a[N],b[N],cnt;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)scanf("%d%d",&x,&y),link(x,y);
    while(m--)
    {
        scanf("%s",s+1);
        if(s[1]=='Q')scanf("%d%d",&x,&y),printf("%s\n",judge(x,y)?"Yes":"No");
        if(s[1]=='C')scanf("%d%d",&x,&y),a[++cnt]=x,b[cnt]=y,cut(x,y);
        if(s[1]=='U')scanf("%d",&x),link(a[x],b[x]);
    }
    return 0;
}
View Code

 

 

 

 

维护链信息：

 

P3203 [HNOI2010]弹飞绵羊

题意： 一条直线上摆放着n个装置 每个装置有一个弹性系数k   表示在这个装置上会弹到这个装置后面的第k个装置上  如果不存在 那么弹上天

　　    操作一： 问从i开始弹 弹多少次上天

　　　操作二： 将第i装置的弹性系数改为x

题解： lct板子题 连一下就行了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v)  memset(A,v,sizeof A)
////////////////////////////////////
const int N=2e6+10;
int fa[N],siz[N],son[N][2],rev[N],st[N];
int get(int x){return son[fa[x]][1]==x||son[fa[x]][0]==x;}
void up(int x){siz[x]=siz[son[x][1]]+siz[son[x][0]]+1;}
void change(int x){swap(son[x][1],son[x][0]);rev[x]^=1;}
void down(int x)
{
    if(!rev[x])return ;rev[x]=0;
    if(son[x][0])change(son[x][0]);
    if(son[x][1])change(son[x][1]);
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=son[fa[x]][1]==x,w=son[x][k^1];
    if(get(y))son[z][son[z][1]==y]=x;son[x][k^1]=y;son[y][k]=w;
    if(w)fa[w]=y;fa[y]=x;fa[x]=z;
    up(y);up(x);
}
void splay(int x)
{
    int y=x,top=0;st[++top]=y;
    while(get(y))st[++top]=y=fa[y];
    while(top)down(st[top--]);
    while(get(x))
    {
        int y=fa[x],z=fa[y];
        if(get(y))rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
        rotate(x);
    }up(x);
}
void access(int x)
{
    for(int y=0;x;x=fa[y=x])
    splay(x),son[x][1]=y,up(x);
}
void makeroot(int x)
{
    access(x);splay(x);change(x);
}
int findroot(int x)
{
    access(x);splay(x);
    while(son[x][0])down(x),x=son[x][0];
    splay(x);return x;
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
    makeroot(x);if(findroot(y)!=x)fa[x]=y;
}
void cut(int x,int y)
{
    split(x,y);
    if(findroot(y)==x&&fa[y]==x&&!son[y][0])
    fa[y]=son[x][1]=0,up(x);
}int n,m,op,x,y,z;
int to[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);link(i,min(n+1,i+x));to[i]=min(n+1,i+x);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&op);
        if(op==1){   scanf("%d",&x);x++;split(x,n+1);printf("%d\n",siz[n+1]-1);}
        else {scanf("%d%d",&x,&y);x++;cut(x,to[x]);link(x,min(n+1,x+y));to[x]=min(n+1,x+y);}
    }
    return 0;
}
View Code

 

P2486 [SDOI2011]染色

 

 题解： 之前用树剖做过一次  树剖维护区间合并非常的麻烦！   这题可以用lct快速水过   因为lct是将链上所有信息扔到splay里 所以直接输出即可

　　　  注意对一段链区间更新信息的时候 和询问一样要split一下  然后对y也就是树根更新一下  然后down下去即可

 

不过相比树剖  lct的常数确实有点大  时间慢了三倍。。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
const int N=2e6+10;
int fa[N],t[N],son[N][2],rev[N],st[N],col[N],lcol[N],rcol[N],tag[N];
int get(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void up(int x)
{
    if(son[x][0])lcol[x]=lcol[son[x][0]];else lcol[x]=col[x];
    if(son[x][1])rcol[x]=rcol[son[x][1]];else rcol[x]=col[x];
    t[x]=t[son[x][0]]+t[son[x][1]]+1-(col[x]==rcol[son[x][0]])-(col[x]==lcol[son[x][1]]);
}
void change(int x){swap(son[x][0],son[x][1]);swap(lcol[x],rcol[x]);rev[x]^=1;}
void update(int x,int y){tag[x]=col[x]=lcol[x]=rcol[x]=y;t[x]=1;}
void down(int x)
{
    if(rev[x])
    {
        rev[x]=0;
        if(son[x][0])change(son[x][0]);
        if(son[x][1])change(son[x][1]);
    }
    if(tag[x])
    {
        if(son[x][0])update(son[x][0],tag[x]);
        if(son[x][1])update(son[x][1],tag[x]);
        tag[x]=0;
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=son[fa[x]][1]==x,w=son[x][k^1];
    if(get(y))son[z][son[z][1]==y]=x;son[x][k^1]=y;son[y][k]=w;
    if(w)fa[w]=y;fa[y]=x;fa[x]=z;
    up(y);up(x);
}
void splay(int x)
{
    int y=x,top=0;st[++top]=y;
    while(get(y))st[++top]=y=fa[y];
    while(top)down(st[top--]);
    while(get(x))
    {
        int y=fa[x],z=fa[y];
        if(get(y))rotate((son[y][0]==x)^(son[z][0]==y)?x:y);rotate(x);
    }up(x);
}
void access(int x)
{
    for(int y=0;x;x=fa[y=x])
    splay(x),son[x][1]=y,up(x);
}
void makeroot(int x)
{
    access(x);splay(x);change(x);
}
int findroot(int x)
{
    access(x);splay(x);
    while(son[x][0])down(x),x=son[x][0];
    splay(x);return x;
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
    makeroot(x);if(findroot(y)!=x)fa[x]=y;
}int n,m,x,y,z;char s[2];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&x),col[i]=lcol[i]=rcol[i]=x,t[i]=1;
    for(int i=1;i<n;i++)scanf("%d%d",&x,&y),link(x,y);
    while(m--)
    {
        scanf("%s",s+1);
        if(s[1]=='Q')scanf("%d%d",&x,&y),split(x,y),printf("%d\n",t[y]);
        if(s[1]=='C')scanf("%d%d%d",&x,&y,&z),split(x,y),update(y,z);
    }
    return 0;
}
View Code

 

 

P1501 [国家集训队]Tree II

 

题解：  注意一下乘法和加法的优先级就行了 

　　　  忘记加siz了导致一直wa 。。。。 其实和线段树是一样的  只是多出了一个点  如果操作保证合法的话 就不用findroot特判了  加速了很多

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
const int N=1e5+10;
const ll mod=51061;
int fa[N],son[N][2],rev[N],st[N],siz[N];
ll sum[N],val[N],mul[N],p[N];
int get(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void up(int x){sum[x]=(sum[son[x][0]]+sum[son[x][1]]+val[x])%mod;siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;}
void change(int x){swap(son[x][0],son[x][1]);rev[x]^=1;}
void add(int x,int y){sum[x]=(sum[x]+siz[x]*y)%mod;val[x]=(val[x]+y)%mod;p[x]=(p[x]+y)%mod;}
void mulit(int x,int y){sum[x]=sum[x]*y%mod;val[x]=val[x]*y%mod;p[x]=p[x]*y%mod;mul[x]=mul[x]*y%mod;}
void down(int x)
{
    if(mul[x]!=1)
    {
        if(son[x][0])mulit(son[x][0],mul[x]);
        if(son[x][1])mulit(son[x][1],mul[x]);
        mul[x]=1;
    }
    if(p[x])
    {
        if(son[x][0])add(son[x][0],p[x]);
        if(son[x][1])add(son[x][1],p[x]);
        p[x]=0;
    }
    if(rev[x])
    {
        rev[x]=0;
        if(son[x][0])change(son[x][0]);
        if(son[x][1])change(son[x][1]);
    }
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=son[y][1]==x,w=son[x][k^1];
    if(get(y))son[z][son[z][1]==y]=x;son[x][k^1]=y;son[y][k]=w;
    if(w)fa[w]=y;fa[y]=x;fa[x]=z;
    up(y);
}
void splay(int x)
{
    int y=x,top=0;st[++top]=y;
    while(get(y))st[++top]=y=fa[y];
    while(top)down(st[top--]);
    while(get(x))
    {
        int y=fa[x],z=fa[y];
        if(get(y))rotate((son[y][0]==x)^(son[z][0]==y)?x:y);
        rotate(x);
    }up(x);
}
void access(int x)
{
    for(int y=0;x;x=fa[y=x])
    splay(x),son[x][1]=y,up(x);
}
void makeroot(int x)
{
    access(x);splay(x);change(x);
}
int findroot(int x)
{
    access(x);splay(x);
    while(son[x][0])down(x),x=son[x][0];
    splay(x);return x;
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
    makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
    split(x,y);
    fa[x]=son[y][0]=0;
}int n,m,x,y,z,t,q;char s[20];
int main()
{   
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)mul[i]=val[i]=siz[i]=1;
    for(int i=1;i<n;i++)scanf("%d%d",&x,&y),link(x,y);
    while(q--)
    {
        scanf("%s",s+1);
        if(s[1]=='+')scanf("%d%d%d",&x,&y,&z),split(x,y),add(y,z);
        if(s[1]=='-')scanf("%d%d%d%d",&x,&y,&z,&t),cut(x,y),link(z,t);
        if(s[1]=='*')scanf("%d%d%d",&x,&y,&z),split(x,y),mulit(y,z);
        if(s[1]=='/')scanf("%d%d",&x,&y),split(x,y),printf("%lld\n",sum[y]);
    }
    return 0;
}
View Code

 

 

维护生成树：

 

P4172 [WC2006]水管局长

题意： 有n个点 m条边 （保证每时每刻任意两点都联通  且路径可能有多条) 

　　　 操作一： 询问   最小化 x 到y 的某条路径的最大边权 

　　　 操作二： 删除x-y的边  

题解： 第一眼很像是最小生成树 但是是动态删边的 

　　　 可以考虑时间回溯  就是一开始有一棵最小生成树  不断地加边   显然加入一个边一定会形成环  那么如果新加入的边比这个环的最大边要大 就不用加  反之  删去最大的边然后加入该边肯定是满足正确性的  这样就可以一直维护一个树形结构

　　　 删边和加边很显然是lct 但是之前做的lct都是点权的   可以拆边  对每个边建立一个虚点  每次连两条边即可  除了虚点其他都是没有权值的  反正不影响答案   因为要删除最大值的边  所以splay维护的是编号  而不是权值  否则删边的时候难以找到这个权值对应的是哪个边

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,m,qq,f[N],vis[N],ans[N];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
struct Edge{int x,y,v;}edge[N];
struct Q{int op,x,y,flag;}q[N];
map<pair<int,int>,int >id;
////lct 
int mx[N],son[N][2],fa[N],rev[N],st[N],val[N];
int get(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void up(int x)
{
    mx[x]=val[x]; 
    if(edge[mx[son[x][0]]].v>edge[mx[x]].v)mx[x]=mx[son[x][0]];
    if(edge[mx[son[x][1]]].v>edge[mx[x]].v)mx[x]=mx[son[x][1]];
}
void change(int x){swap(son[x][0],son[x][1]);rev[x]^=1;}
void down(int x)
{
    if(!rev[x])return ;rev[x]=0;
    if(son[x][0])change(son[x][0]);
    if(son[x][1])change(son[x][1]);
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=son[fa[x]][1]==x,w=son[x][k^1];
    if(get(y))son[z][son[z][1]==y]=x;son[x][k^1]=y;son[y][k]=w;
    if(w)fa[w]=y;fa[y]=x;fa[x]=z;
    up(y);
}
void splay(int x)
{
    int y=x,top=0;st[++top]=y;
    while(get(y))st[++top]=y=fa[y];
    while(top)down(st[top--]);
    while(get(x))
    {
        int y=fa[x],z=fa[y];
        if(get(y))rotate((son[y][0]==x)^(son[z][0]==y)?x:y);rotate(x);
    }up(x);
}
void access(int x)
{
    for(int y=0;x;x=fa[y=x])
    splay(x),son[x][1]=y,up(x);
}
void makeroot(int x)
{
    access(x);splay(x);change(x);
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
    makeroot(x);fa[x]=y;
}
void cut(int x,int y)
{
    split(x,y);fa[x]=son[y][0]=0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&qq);int x,y,z;for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        if(x>y)swap(x,y);
        edge[i]=(Edge){x,y,z};
    }
    sort(edge+1,edge+1+m,[](Edge a,Edge b){return a.v<b.v;});
    for(int i=1;i<=m;i++)id[{edge[i].x,edge[i].y}]=i;
    for(int i=1;i<=qq;i++)
    {
        scanf("%d%d%d",&x,&y,&z);if(y>z)swap(y,z);
        q[i]=(Q){x,y,z};
        if(x==2)
        {
            vis[id[{y,z}]]=1;q[i].flag=id[{y,z}];
        }
    }
    for(int i=n+1;i<=n+m;i++)mx[i]=val[i]=i-n;//给每条边预处理一个虚点  等等直接用就行了
    int cnt=0;
    for(int i=1;i<=m;i++)if(!vis[i])//先维护一个最小生成树
    {
        if(find(edge[i].x)==find(edge[i].y))continue;
        f[find(edge[i].x)]=find(edge[i].y);
        link(edge[i].x,i+n);link(edge[i].y,i+n);
        cnt++;
        if(cnt==n-1)break;
    }
    for(int i=qq;i>=1;i--)
    {   
        x=q[i].x;y=q[i].y;
        if(q[i].op==1)
        {
            split(x,y);ans[i]=edge[mx[y]].v;
        }
        else 
        {   
            split(x,y);
            int d=q[i].flag,t=mx[y];
            if(edge[d].v<edge[t].v)
            {
                cut(edge[t].x,t+n);cut(edge[t].y,t+n);
                link(x,d+n);link(y,d+n);
            }
        }
    }
    for(int i=1;i<=qq;i++)
    if(q[i].op==1)printf("%d\n",ans[i]);
    return 0;
}
View Code

 

P2387 [NOI2014]魔法森林

题意： 有一个包含n个点m条边的无向图  每条边有a b两个值  要经过这条边  a属性要大于a值 b属性要大于b值 

　　　 问 $min   sum(a+b) $ 使得能从1走到n

题解:  看起来像两棵最小生成树 其实可以用排序去掉一棵 类似水管局长地维护即可

　　

#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n,m,qq,f[N],vis[N],ans[N];
struct Edge{int x,y,a,v;}edge[N];

int maxx[N],son[N][2],fa[N],rev[N],st[N],val[N];
int get(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;}
void up(int x)
{
    maxx[x]=val[x];
    if(edge[maxx[son[x][0]]].v>edge[maxx[x]].v)maxx[x]=maxx[son[x][0]];
    if(edge[maxx[son[x][1]]].v>edge[maxx[x]].v)maxx[x]=maxx[son[x][1]];
}
void change(int x){swap(son[x][0],son[x][1]);rev[x]^=1;}
void down(int x)
{
    if(!rev[x])return ;rev[x]=0;
    if(son[x][0])change(son[x][0]);
    if(son[x][1])change(son[x][1]);
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],k=son[fa[x]][1]==x,w=son[x][k^1];
    if(get(y))son[z][son[z][1]==y]=x;son[x][k^1]=y;son[y][k]=w;
    if(w)fa[w]=y;fa[y]=x;fa[x]=z;
    up(y);
}
void splay(int x)
{
    int y=x,top=0;st[++top]=y;
    while(get(y))st[++top]=y=fa[y];
    while(top)down(st[top--]);
    while(get(x))
    {
        int y=fa[x],z=fa[y];
        if(get(y))rotate((son[y][0]==x)^(son[z][0]==y)?x:y);rotate(x);
    }up(x);
}
void access(int x)
{
    for(int y=0;x;x=fa[y=x])
    splay(x),son[x][1]=y,up(x);
}
void makeroot(int x)
{
    access(x);splay(x);change(x);
}
void split(int x,int y)
{
    makeroot(x);access(y);splay(y);
}
void link(int x,int y)
{
    makeroot(x);fa[x]=y;
}
int findroot(int x)
{
    access(x);splay(x);
    while(son[x][0])down(x),x=son[x][0];
    return x;
}
void cut(int x,int y)
{
    split(x,y);fa[x]=son[y][0]=0;
}
int a,b,c,d,x,y;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        edge[i]=(Edge){a,b,c,d};
    }
    sort(edge+1,edge+1+m,[](Edge a,Edge b){return a.a<b.a||a.a==b.a&&a.v<b.v;});
    int ans=1e9;
    for(int i=n+1;i<=n+m;i++)val[i]=maxx[i]=i-n;
    for(int i=1;i<=m;i++)
    {   
        x=edge[i].x;y=edge[i].y;a=edge[i].a;b=edge[i].v;
        if(findroot(x)==findroot(y))
        {
            split(x,y);int t=maxx[y];
            if(edge[t].v>b)cut(edge[t].x,t+n),cut(edge[t].y,t+n);
            else continue;
        }
        link(x,i+n),link(y,i+n);
        if(find(1)==find(n))
        {   
            split(1,n);int t=maxx[n];
            ans=min(ans,a+edge[t].v);
        }
    }
    cout<<ans;
    return 0;
}
View Code

 

推荐阅读