UOJ#3 【NOI2014】魔法森林
把边按照\(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;
}