传送门

把边按照$a_i$升序排序。

每次加入一条边,如果两端不连通,则直接加入,否则加入以后就会出现一个环,割掉这个环上$b_i$最大的边。

每次加入一条边后计算当前答案取最大值。

本蒟蒻手一抽在splay中写下了如下代码

    void splay(int x){
        push_tag(x);
        while(ntr(x)){
            int f=fa[x];
            if(ntr(f))if(fx(x)^fx(f))rotate(x);
            else rotate(x);
            rotate(x);
        }
    }

其中ntr(x)表示x是否为根。

fx(x)表示x为x父亲的哪边子树。

然后就变成了单旋。

然后一个下午都在Extra Test Failed: Time Limit Exceeded on 15。

/*
Author: CNYALI_LK
LANG: C++
PROG: 3.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
    int cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
    putchar(end);
}
struct Edge{
    int u,v,a,b;
    void init(){
        u=read();v=read();a=read();b=read();
    }
};

const int N=201011;
Edge edge[N];
int cmp(Edge a,Edge b){return a.a<b.a;}
int w[N];

int n,m;
struct Link_Cut_Tree{
    int mx[N],son[N][2],n,mxa[N],rev[N],fa[N];
    void newpoint(){
        mxa[++n]=n;
        mx[n]=w[n];
    }
#define ntr(x) (fa[x]&&(son[fa[x]][1]==x||son[fa[x]][0]==x))
    void push_up(int x){
        mx[x]=w[x];
        mxa[x]=x;
        if(chkmax(mx[x],mx[son[x][0]]))mxa[x]=mxa[son[x][0]];
        if(chkmax(mx[x],mx[son[x][1]]))mxa[x]=mxa[son[x][1]];
    }
    void push_tag(int x){
        if(ntr(x))push_tag(fa[x]);
        if(rev[x]){
            swap(son[x][0],son[x][1]);
            rev[son[x][0]]^=1;
            rev[son[x][1]]^=1;
            rev[x]=0;
        }
    }
#define fx(x) (son[fa[x]][1]==x)
    void rotate(int x){
        int f=fa[x],g=fa[f],s=fx(x);
        if(ntr(f))son[g][fx(f)]=x;
        fa[x]=g;
        fa[f]=x;
        son[f][s]=son[x][s^1];
        fa[son[f][s]]=f;
        son[x][s^1]=f;
        push_up(f);
        push_up(x);
    }
    void splay(int x){
        push_tag(x);
        while(ntr(x)){
            int f=fa[x];
            if(ntr(f))if(fx(x)^fx(f))rotate(x);
            else rotate(f);
            rotate(x);
        }
    }
    void access(int x){
        int y=0;
        while(x){
            splay(x);   
            son[x][1]=y;
            push_up(x);
            y=x;x=fa[x];
        }
    }
    void as(int x){access(x);splay(x);}
    void mtr(int x){as(x);rev[x]^=1;}
    void link(int u,int v){

        mtr(u);
        access(v);

        fa[u]=v;
    }
    void cut(int u,int v){
        mtr(u);
        as(v);
        fa[u]=son[v][0]=0;
        push_up(v);
    }
    int query(int u,int v){
        mtr(u);
        as(v);
        return mxa[v];
    }
    int fr(int x){

        as(x);
        while(son[x][0])x=son[x][0];
        return x;
    }
};
Link_Cut_Tree lct;
void link(int s,int u,int v){
    if(lct.fr(u)!=lct.fr(v))lct.link(u,s),lct.link(s,v);
    else{
        int hq=lct.query(u,v);
        if(w[hq]>w[s]){
            lct.cut(hq,edge[hq-n].v);
            lct.cut(hq,edge[hq-n].u);
            lct.link(u,s);
            lct.link(s,v);
        }
    }
}
int query(int u,int v){
    if(lct.fr(u)!=lct.fr(v))return 0x3f3f3f3f;
    return w[lct.query(u,v)];   
}
int main(){
#ifdef cnyali_lk
    freopen("3.in","r",stdin);
    freopen("3.out","w",stdout);
#endif
    n=read();
    m=read();
    for(int i=1;i<=n;++i)lct.newpoint();
    for(int i=1;i<=m;++i)edge[i].init();
    sort(edge+1,edge+m+1,cmp);
    int ans=0x3f3f3f3f;
    for(int i=1;i<=m;++i){
        lct.newpoint();

        w[i+n]=edge[i].b;

        link(i+n,edge[i].u,edge[i].v);

        chkmin(ans,edge[i].a+query(1,n));

    }
    if(ans==0x3f3f3f3f)printf("-1\n");
    else printf("%d\n",ans);
    return 0;
}

标签: LCT

添加新评论