首页 > 其他 > 详细

[NOI2014]魔法森林

时间:2018-12-11 10:17:11      阅读:169      评论:0      收藏:0      [点我收藏+]

[NOI2014]魔法森林

UOJ
BZOJ
luogu
把边以a为关键字从小到大排序,对b用lct维护最小生成树
此题可以并查集维护连通性,lct的findroot速度感人

#include<bits/stdc++.h>
using namespace std;
const int _=2e5+5,inf=1e9;
int re(){
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int n,m,ans=inf,top;
int f[_],w[_],id[_],fa[_],st[_],rev[_],ch[2][_];
struct edge{int u,v,a,b;}e[_];
bool cmp(edge x,edge y){return x.a<y.a;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
bool son(int x){return x==ch[1][fa[x]];}
bool isrt(int x){return ch[1][fa[x]]!=x&&ch[0][fa[x]]!=x;}
void rever(int x){if(x)swap(ch[0][x],ch[1][x]),rev[x]^=1;}
void pd(int x){if(rev[x])rever(ch[0][x]),rever(ch[1][x]),rev[x]=0;}
void pu(int x){
    id[x]=x;
    if(ch[0][x]&&w[id[ch[0][x]]]>w[id[x]])id[x]=id[ch[0][x]];
    if(ch[1][x]&&w[id[ch[1][x]]]>w[id[x]])id[x]=id[ch[1][x]];
}
void rotate(int x){
    int y=fa[x],z=fa[y],k=son(x);
    ch[k][y]=ch[k^1][x];if(ch[k][y])fa[ch[k][y]]=y;
    fa[x]=z;if(!isrt(y))ch[son(y)][z]=x;
    ch[k^1][x]=y;fa[y]=x;pu(y);
}
void splay(int x){
    st[top=1]=x;
    for(int i=x;!isrt(i);i=fa[i])st[++top]=fa[i];
    while(top)pd(st[top--]);
    for(int y=fa[x];!isrt(x);rotate(x),y=fa[x])
        if(!isrt(y))rotate(son(y)^son(x)?x:y);
    pu(x);
}
void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),ch[1][x]=y;pu(x);}
void makert(int x){access(x);splay(x);rever(x);}
void split(int x,int y){makert(x);access(y);splay(y);}
void link(int x,int y){makert(x);fa[x]=y;}
void cut(int x,int y){split(x,y);ch[0][y]=fa[x]=0;pu(y);}
int query(int x,int y){split(x,y);return id[y];}
int main(){
    n=re(),m=re();
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        e[i].u=re(),e[i].v=re();
        e[i].a=re(),e[i].b=re();
    }
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++){
        int x=e[i].u,y=e[i].v;
        if(find(x)==find(y)){
            int z=query(x,y);
            if(w[z]>e[i].b)
                cut(e[z-n].u,z),cut(e[z-n].v,z);
            else continue;
        }
        else f[f[x]]=f[y];
        w[i+n]=e[i].b;id[i+n]=i+n;
        link(x,i+n);link(y,i+n);
        if(find(1)==find(n))ans=min(ans,e[i].a+w[query(1,n)]);
    }
    printf("%d\n",ans==inf?-1:ans);
    return 0;
}

[NOI2014]魔法森林

原文:https://www.cnblogs.com/sdzwyq/p/10100313.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!