【BZOJ3669】魔法森林

    先将所有的边按a从小到大排序，然后依次加入边维护b的最小生成树，用LCT实现。

    边当点加。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=50010,maxm=100010,inf=~0U>>1;

struct LCT
{
	struct Node
	{
		Node *c[2],*p,*lcp,*maxv;
		int v;
		int tag_rev;
		int w() {return p->c[1]==this;}
	}*Null,*ND[maxn],*ED[maxm];

	#define ls x->c[0]
	#define rs x->c[1]

	void Update(Node *x)
	{
		if (x==Null) return;
		x->maxv=x;
		if (ls->maxv->v>x->maxv->v) x->maxv=ls->maxv;
		if (rs->maxv->v>x->maxv->v) x->maxv=rs->maxv; 
	}

	void Mark_Rev(Node *x)
	{
		swap(ls,rs);
		x->tag_rev^=1;
	}

	void Push_Down(Node *x)
	{
		if (!x->tag_rev) return;
		Mark_Rev(ls);
		Mark_Rev(rs);
		x->tag_rev=0;
	}

	void Rotate(Node *x)
	{
		Node *p=x->p;
		int w=x->w();
		Push_Down(p);Push_Down(x);
		x->lcp=p->lcp;p->lcp=Null;
		p->p->c[p->w()]=x;x->c[!w]->p=p;
		x->p=p->p;p->c[w]=x->c[!w];
		x->c[!w]=p;p->p=x;
		Update(p);
	}

	void Splay(Node *x)
	{
		if (x==Null) return;
		Push_Down(x);
		while (x->p!=Null)
		{
			if (x->p->p==Null) {Rotate(x);break;}
			if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		}
		Update(x);
	}

	void Access(Node *x)
	{
		Node *v=Null,*pre=x;
		while (x!=Null)
		{
			Splay(x);
			rs->lcp=x;
			rs->p=Null;
			rs=v;
			v->p=x;
			v->lcp=Null;
			Update(x);
			v=x;x=x->lcp;
		}
		Splay(pre);
	}

	Node* Find_Root(Node *x)
	{
		Access(x);
		while (ls!=Null) Push_Down(x),x=ls;
		Splay(x);
		return x;
	}

	void Set_Root(Node *x)
	{
		Access(x);
		Mark_Rev(x);
	}

	Node* Prev(Node *x)
	{
		Splay(x);
		if (rs==Null) return Null;
		Push_Down(x);x=rs;
		while (ls!=Null) Push_Down(x),x=ls;
		Splay(x);
		return x;
	}

	void Link(Node *x,Node *v)
	{
		Set_Root(x);
		x->lcp=v;
		Access(x);
	}

	void Cut(Node *x)
	{
		Access(x);
		ls->p=Null;
		ls=Null;
		Update(x);
	}

	void Init(int n,int m)
	{
		for (int i=0;i<=n;i++) ND[i]=new Node;
		for (int i=1;i<=m;i++) ED[i]=new Node;
		Null=ND[0];
		for (int i=0;i<=n;i++) ND[i]->c[0]=ND[i]->c[1]=ND[i]->p=ND[i]->lcp=ND[i]->maxv=Null,ND[i]->v=ND[i]->tag_rev=0;
		for (int i=1;i<=m;i++) ED[i]->c[0]=ED[i]->c[1]=ED[i]->p=ED[i]->lcp=Null,ED[i]->maxv=ED[i],ED[i]->v=ED[i]->tag_rev=0;
	}

	void Link(int x,int y,int e)
	{
		Link(ND[x],ED[e]);
		Link(ED[e],ND[y]);
	}
	
	bool Connected(int x,int y) {return Find_Root(ND[x])==Find_Root(ND[y]);}

	Node* Max_Edge(Node *x,Node *y)
	{
		Set_Root(x);
		Access(y);
		return y->maxv;
	}

	void Cut_MaxEdge(int x,int y)
	{
		Node *e=Max_Edge(ND[x],ND[y]);
		Cut(Prev(e)),Cut(e);
	}
	
	int Max_Edge_V(int x,int y) {return Max_Edge(ND[x],ND[y])->v;}
	
	#undef ls
	#undef rs
}T;

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

struct Edge
{
	int x,y,a,b;
	bool operator< (const Edge &b) const {return a<b.a;}
}E[maxm];

int n,m;

void Init()
{
	read(n),read(m);
	for (int i=1;i<=m;i++) read(E[i].x),read(E[i].y),read(E[i].a),read(E[i].b);
	sort(E+1,E+1+m);
	T.Init(n,m);
	for (int i=1;i<=m;i++) T.ED[i]->v=E[i].b;
}

void Kruskal()
{
	int ans=inf;
	int cnt=0;
	for (int i=1;i<=m;i++)
	{
		if (T.Connected(E[i].x,E[i].y))
		{
			if (T.Max_Edge_V(E[i].x,E[i].y)>E[i].b)
				T.Cut_MaxEdge(E[i].x,E[i].y),T.Link(E[i].x,E[i].y,i);;
		}
		else T.Link(E[i].x,E[i].y,i);
		if (T.Connected(1,n))
		{
			int b=T.Max_Edge_V(1,n);
			if (E[i].a+b<ans) ans=E[i].a+b;
		}
	}
	if (ans==inf) printf("-1\n");
	else printf("%d\n",ans);
}

int main()
{
	Init();
	Kruskal();
	return 0;
}