传送门

高级数据结构学傻系列

正解似乎是最短路xjb搞，但是用LCT瞎搞搞也是很吼啊。

从贪心开始，按照每条边a的大小随意sort一下。

对于每个边，我们check两点的联通性，如果联通的话取b最大的值，如果大于当前边的b的话就就删除最大边，把这条边加进去。

如果不连通的话直接添加即可。

LCT滋次这些操作，所以大力LCT即可。

//BZOJ 3669//by Cydiater//2017.2.16#include <iostream>#include <queue>#include <map>#include <cstring>#include <string>#include <iomanip>#include <ctime>#include <cstdlib>#include <cstdio>#include <iomanip>#include <algorithm>#include <bitset>#include <set>#include <vector>#include <complex>using namespace std;#define ll long long#define up(i,j,n)	for(int (i)=(j);(i)<=(n);(i)++)#define down(i,j,n)	for(int (i)=(j);(i)>=(n);(i)--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define FILE		"magicalforest"const int MAXN=1e6+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,M,len=0,ans=oo;struct edge{	int x,y,a,b;}e[MAXN];namespace LCT{	struct SplayTree{		int son[2],Max,val,fa,tag,id;		void clear(){son[0]=son[1]=Max=val=fa=0;}	}t[MAXN];	inline int isrt(int k){return t[k].fa==0||(t[t[k].fa].son[0]!=k&&t[t[k].fa].son[1]!=k);}	inline int get(int k){return t[t[k].fa].son[1]==k;}	inline void rev(int k){		if(!k)return;		swap(t[k].son[0],t[k].son[1]);		t[k].tag^=1;	}	inline void reload(int k){		if(!k)return;		t[k].Max=t[k].val;t[k].id=k;		int s1=t[k].son[0],s2=t[k].son[1];		if(t[s1].Max>t[k].Max){			t[k].Max=t[s1].Max;			t[k].id=t[s1].id;		}		if(t[s2].Max>t[k].Max){			t[k].Max=t[s2].Max;			t[k].id=t[s2].id;		}	}	inline void Pushdown(int k){		if(!k)return;		if(t[k].tag){			rev(t[k].son[0]);rev(t[k].son[1]);			t[k].tag^=1;		}	}	inline void rotate(int k){		int old=t[k].fa,oldf=t[old].fa,which=get(k);		if(!isrt(old))t[oldf].son[t[oldf].son[1]==old]=k;		t[old].son[which]=t[k].son[which^1];t[t[old].son[which]].fa=old;		t[k].son[which^1]=old;t[old].fa=k;t[k].fa=oldf;t[0].clear();		reload(old);reload(k);	}	int stack[MAXN],top=0;	inline void splay(int k){		top=0;stack[++top]=k;		for(int tmp=k;!isrt(tmp);tmp=t[tmp].fa){			stack[++top]=t[tmp].fa;		}		while(top)Pushdown(stack[top--]);		while(!isrt(k)){			int fa=t[k].fa;			if(!isrt(fa))rotate(get(fa)==get(k)?fa:k);			rotate(k);		}	}	inline void access(int k){		int tmp=0;		while(k){			splay(k);t[k].son[1]=tmp;			reload(k);tmp=k;k=t[k].fa;		}	}	void mrt(int k){		access(k);splay(k);rev(k);	}	int grt(int k){		access(k);splay(k);		while(t[k].son[0])k=t[k].son[0];		return k;	}	void Link(int x,int y){		mrt(x);t[x].fa=y;	}	void Cut(int x,int y){		mrt(x);access(y);splay(y);t[y].son[0]=t[x].fa=0;		reload(y);	}	int col(int x,int y){		mrt(x);access(y);splay(y);		return t[y].id;	}}int cnt;namespace solution{	inline bool cmp(edge x,edge y){return x.a<y.a;}	void Prepare(){		N=read();M=read();		cnt=N;		up(i,1,M){			int x=read(),y=read(),a=read(),b=read();			e[++len]=(edge){x,y,a,b};		}		sort(e+1,e+M+1,cmp);	}	void Solve(){		up(i,1,M){			cnt++;			int x=e[i].x,y=e[i].y,a=e[i].a,b=e[i].b;			if(LCT::grt(x)!=LCT::grt(y)){				LCT::t[cnt].Max=b;				LCT::t[cnt].val=b;				LCT::t[cnt].id=cnt;				LCT::Link(x,cnt);				LCT::Link(cnt,y);			}			else{				int id=LCT::col(x,y);				if(LCT::t[id].val<=b)continue;				LCT::Cut(e[id-N].x,id);				LCT::Cut(e[id-N].y,id);				LCT::t[cnt].Max=b;				LCT::t[cnt].val=b;				LCT::t[cnt].id=cnt;				LCT::Link(x,cnt);				LCT::Link(cnt,y);			}			if(LCT::grt(1)==LCT::grt(N)){				int id=LCT::col(1,N);				cmin(ans,a+LCT::t[id].val);			}		}		if(ans==oo)ans=-1;		cout<<ans<<endl;	}}int main(){	using namespace solution;	Prepare();	Solve();	return 0;}

BZOJ3669: [Noi2014]魔法森林