[洛谷P2387][NOI2014]魔法森林

墨蓝 2023-06-05 12:40 13阅读 0赞

题目描述：[https://www.luogu.org/problem/P2387][https_www.luogu.org_problem_P2387]

解析：题目要求的是最大值最小，首先想到二分，但有两个变量不好搞，于是想到一个显然的贪心：对于两个点u.v，他们之间的边a值小，b值也小的边肯定更优。所以我们先将边按a值排序，然后按b值来维护最小生成树。对于一条新插入的边，如果它已经出现在了这颗最小生成树中，那么我们查询这个环中最大的边是否比这个边大，如果是，那么断掉原来的那条边。那么我么怎样维护这颗最小生成树呢？显然就是LCT了。但我们要维护的是边值，怎么搞呢?一个套路就是多建一个点，然后将这个点的值赋为边权，起点与终点分别连向这条边即可。

细节：1.没什么细节，不要写挂就好。

附上代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<algorithm> 
    using namespace std;
    
    //给定一个图，每个边有两个权值a.b,求起点到给定点的一条路径
    //使得这条路径上a的最大值与b的最大值的和最小 
    
    const int MAXN=50005,MAXM=200005;
    int n,m;
    struct Edge{
        int u,v,a,b;
    }edge[MAXM];
    int fa[MAXM];
    struct Node{
        int max,val,son[2],fa;
        bool flag_reverse;
    }node[MAXM<<1];
    int ans=0x3f3f3f;
    int stk[MAXM<<1];
    
    inline int read(){
        int ret=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){
         if(c=='-') f=-f;c=getchar();}
        while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
        return ret*f;
    }
    
    void readIn(int i){
        edge[i].u=read();edge[i].v=read();edge[i].a=read();edge[i].b=read();
        edge[i+1].u=edge[i].u;edge[i+1].v=edge[i].v;edge[i+1].a=edge[i].a;edge[i+1].b=edge[i].b;
    }
    
    int union_find(int x){
        if(x==fa[x]) return x;
        else return fa[x]=union_find(fa[x]);
    }
    
    void update(int x){
        node[x].max=x;
        int lson=node[x].son[0],rson=node[x].son[1];
        if(lson&&node[node[lson].max].val>node[node[x].max].val) node[x].max=node[lson].max;
        if(rson&&node[node[rson].max].val>node[node[x].max].val) node[x].max=node[rson].max;
    }
    
    void pushdown(int x){
        if(node[x].flag_reverse){
            int lson=node[x].son[0],rson=node[x].son[1];
            node[lson].flag_reverse^=1;
            node[rson].flag_reverse^=1;
            node[x].flag_reverse^=1;
            swap(node[x].son[0],node[x].son[1]);        
        } 
    }
    
    int get(int x){
        return x==node[node[x].fa].son[0]||x==node[node[x].fa].son[1];
    }
    
    int check(int x){
        return x==node[node[x].fa].son[1];
    }
    
    void rotate(int x){
        int y=node[x].fa,z=node[y].fa,d=check(x),xx=node[x].son[d^1];
        node[y].son[d]=xx;if(xx) node[xx].fa=y;
        if(get(y)) node[z].son[check(y)]=x;node[x].fa=z;
        node[x].son[d^1]=y;node[y].fa=x;
        update(y);update(x);
    }
    
    void splay(int x){
        int y=x,top=0;stk[++top]=y;
        while(get(y)) stk[++top]=y=node[y].fa;
        while(top) pushdown(stk[top--]);
        while(get(x)){
            int y=node[x].fa;
            if(get(y))
                rotate(check(x)==check(y)?y:x);
            rotate(x);
        }
    } 
    
    void access(int x){
        int xx=0;
        while(x){
            splay(x);
            node[x].son[1]=xx;
            xx=x;
            update(x);
            x=node[x].fa;
        }
    }
    
    int find(int x){
        access(x);splay(x);
        while(node[x].son[0]) x=node[x].son[0];
        return x;
    }
    
    void make_root(int x){
        access(x);splay(x);
        node[x].flag_reverse^=1;
    }
    
    void link(int x,int y){
        make_root(x);if(find(y)!=x) node[x].fa=y;
    }
    
    void split(int x,int y){
        make_root(x);access(y);splay(y);
    }
    
    void cut(int x,int y){
        split(x,y);
        if(find(y)==x&&!node[x].son[1]&&node[x].fa==y)
            node[x].fa=node[y].son[0]=0;
    }
    
    int query(int x,int y){
        split(x,y);
        return node[y].max;
    }
    
    void work(){
        for(int i=1;i<=m;++i) fa[i]=i;
        for(int i=1;i<=m;i++){
            int u=edge[i].u,v=edge[i].v;
            if(union_find(u)==union_find(v)){
                int t=query(u,v);
                if(edge[i].b<node[t].val){
                    cut(t,edge[t-n].u);
                    cut(t,edge[t-n].v);
                }
                else{
                    if(union_find(1)==union_find(n))
                        ans=min(ans,edge[i].a+node[query(1,n)].val);
                    continue;
                }
            }
            else fa[union_find(u)]=union_find(v);
            node[i+n].max=i+n;node[i+n].val=edge[i].b;
            link(u,i+n);link(i+n,v);
            if(union_find(1)==union_find(n))
                ans=min(ans,edge[i].a+node[query(1,n)].val);
        }
        if(ans!=0x3f3f3f)
            printf("%d",ans);
        else 
            printf("-1"); 
    }
    
    bool cmp(Edge A,Edge B){
        return A.a<B.a;
    }
    
    int main(){
        n=read();m=read();m<<=1;
        for(int i=1;i<=m;i+=2) readIn(i);
        sort(edge+1,edge+m+1,cmp);
        work();
        return 0;
    }

转载于:https://www.cnblogs.com/JoshDun/p/11324299.html

[https_www.luogu.org_problem_P2387]: https://www.luogu.org/problem/P2387
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/dd73894004a74a5bb1de9dd14c87601d.png