CF603E Pastoral Oddities

我会带着你远行 2021-12-23 15:01 118阅读 0赞

[CF603E Pastoral Oddities][CF603E_Pastoral Oddities]

度数不好处理。转化题意：不存在连通块为奇数时候就成功了（自底向上调整法证明）

暴力：从小到大排序加入。并查集维护。全局变量记录奇数连通块的个数

答案单调不增？

类似整体二分。（其实类似决策单调性）

横纵劈开，提前加入不会影响的边，复杂度得以保证

按秩合并并查集撤销

**值域的访问，不用每次排序，答案一定是某个边的边权，提前排好序。直接访问即可**

#include<bits/stdc++.h>
    #define reg register int
    #define il inline
    #define numb (ch^'0')
    using namespace std;
    typedef long long ll;
    il void rd(int &x){
        char ch;x=0;bool fl=false;
        while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
        for(x=numb;isdigit(ch=getchar());x=x*10+numb);
        (fl==true)&&(x=-x);
    }
    namespace Miracle{
    const int N=100000+5;
    const int M=300000+5;
    int n,m;
    struct node{
        int a,b,c;
        int id;
        bool friend operator <(node a,node b){
            return a.c<b.c;
        }
    }q[M],p[M];
    int fa[N],sz[N];
    struct po{
        int x,y,del;
        po(){}
        po(int xx,int yy,int dd){
            x=xx;y=yy;del=dd;
        }
    }sta[M];
    int top;
    int odd;
    int ans[M];
    int fin(int x){
        return fa[x]==x?x:fin(fa[x]);
    }
    void merge(int x,int y){
        x=fin(x),y=fin(y);
        if(x==y) return;
        if(sz[x]>sz[y]) swap(x,y);
        po now=po(x,y,0);
        if((sz[x]&1)&&(sz[y]&1)){
            now.del=2;
            odd-=2;
        }
        sta[++top]=now;
        fa[x]=y;
        sz[y]+=sz[x];
    }
    void dele(){
        po now=sta[top];
        odd+=now.del;
        sz[now.y]-=sz[now.x];
        fa[now.x]=now.x;
        --top;
    }
    void divi(int l,int r,int lo,int hi){
        if(l>r) return;
    //    cout<<" divi "<<l<<" "<<r<<" : "<<lo<<" "<<hi<<endl;
        int las=top;
        //cout<<" las "<<las<<endl;
        int mid=(l+r)>>1;
        int ans_mid=-1;
        for(reg i=l;i<=mid;++i){
            if(q[i].id<lo) merge(q[i].a,q[i].b);
        }
        for(reg i=lo;i<=hi;++i){
            if(p[i].id<=mid) merge(p[i].a,p[i].b);
            if(odd==0) {
                ans_mid=i;break;
            }
        }
        while(top!=las) dele();
        
        
        //cout<<mid<<" ans_mid "<<ans_mid<<endl;
        if(ans_mid==-1){
            for(reg i=l;i<=mid;++i) ans[i]=-1;
            for(reg i=l;i<=mid;++i){
                if(q[i].id<lo) merge(q[i].a,q[i].b);
            }
            divi(mid+1,r,lo,hi);
            while(top!=las) dele();
            return;
        }
        ans[mid]=p[ans_mid].c;
        
        for(reg i=lo;i<ans_mid;++i){
            if(p[i].id<l) merge(p[i].a,p[i].b);
        }
        divi(l,mid-1,ans_mid,hi);
        while(top!=las) dele();
        
        for(reg i=l;i<=mid;++i){
            if(q[i].id<lo) merge(q[i].a,q[i].b);
        }
        divi(mid+1,r,lo,ans_mid);
        while(top!=las) dele();
        
    }
    int main(){
        rd(n);rd(m);
        odd=n;
        if(n&1){
            for(reg i=1;i<=m;++i){
                puts("-1");
            }return 0;
        }
        for(reg i=1;i<=m;++i){
            rd(q[i].a);rd(q[i].b);rd(q[i].c);
            p[i]=q[i];p[i].id=i;
        }
        sort(p+1,p+m+1);
        for(reg i=1;i<=m;++i) q[p[i].id].id=i;
        for(reg i=1;i<=n;++i) fa[i]=i,sz[i]=1;
        divi(1,m,1,m);
        for(reg i=1;i<=m;++i){
            printf("%d\n",ans[i]);
        }
        return 0;
    }    
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
       Date: 2019/3/5 19:27:14
    */

从整体入手，发现答案不增。类似二分缩小范围。不会影响答案的边提前加上减少复杂度。

转载于:https://www.cnblogs.com/Miracevin/p/10483649.html

[CF603E_Pastoral Oddities]: https://www.luogu.org/problemnew/show/CF603E