题目描述

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 1 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无 向图中的每一条边 ei 包含两个权值 ai 与 bi 。若身上携带的 A 型守护精灵个数不 少于 ai ，且 B 型守护精灵个数不少于 bi ，这条边上的妖怪就不会对通过这条边 的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到 隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的 个数与 B 型守护精灵的个数之和。

输入输出格式

输入格式：

输入文件的第 1 行包含两个整数 n,m，表示无向图共有 n 个节点，m 条边。 接下来 m 行，第i+ 1 行包含 4 个正整数 Xi,Yi,ai,bi，描述第i条无向边。 其中Xi与 Yi为该边两个端点的标号，ai 与 bi 的含义如题所述。 注意数据中可能包含重边与自环。

输出格式：

输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携 带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出“-1”（不 含引号）。

输入输出样例

4 5

1 2 19 1

2 3 8 12

2 4 12 15

1 3 17 8

3 4 1 17 

32

3 1

1 2 1 1 

-1

说明

• 解释1

如果小 E 走路径 1→2→4，需要携带 19+15=34 个守护精灵； 如果小 E 走路径 1→3→4，需要携带 17+17=34 个守护精灵； 如果小 E 走路径 1→2→3→4，需要携带 19+17=36 个守护精灵； 如果小 E 走路径 1→3→2→4，需要携带 17+15=32 个守护精灵。 综上所述，小 E 最少需要携带 32 个守护精灵。

• 解释2

小 E 无法从 1 号节点到达 3 号节点，故输出-1。

题解

刚学完link cut tree，找题刷刷

这道题要满足两种权值和最小，我们难以同时兼顾，我们就先令a最小并维护b最小。

这就成了维护动态最小生成树

将边按a的大小升序排序，不断加边，这样子当前a的路径最大权值如果改变，那么一定是刚加入的边的权值

证明：

1、若路径经过新加入的边，由于新加入的边比之前加入的边权值都大，所以最大权值是新加入的边

2、若路径不经过新加入的边，那么这条路径之前一定被计算过，不妨令之前算出a0+b0，如今算出a1+b0，由升序得a1>a0，所以新算的路径不会被考虑，不影响结果

如此以来，我们按a升序加入，同时维护b的最小生成树【也就是当边为N-1条之后，没加入一条边就删去一条b权值最大的边，动态维护b的最小生成树】

每次统计的答案就是     当前加入的a+【1到N】b的最大值

很明显用link cut tree

把边看作点，每次加入一条边就连上两端的点，删去类似。

我们对每个节点维护子树的最大值编号，每次就可以通过link cut tree找到最大权值对应的边删去，也可以迅速统计路径b最大权值

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define isr(u) (e[e[u].f].ch[1] == u)

#define isrt(u) (!e[u].f || (e[e[u].f].ch[0] != u &&e[e[u].f].ch[1] != u))

using namespace std;

const int maxn=200005,maxm=100005,INF=100000000;

inline int read(){

	int out=0,flag=1;char c=getchar();

	while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}

	while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}

	return out*flag;

}

int N,M,temp[maxn];

struct EDGE{

	int x,y,a,b;

}edge[maxm];

inline bool operator < (const EDGE& a,const EDGE& b){

	return a.a < b.a;

}

struct node{

	int w,f,ch[2],rev,Maxu;

	node() {f = ch[0] = ch[1] = rev = w = 0;}

}e[maxn];

inline void push_up(int u){

	e[u].Maxu = u;

	if (e[u].ch[0] && e[e[e[u].ch[0]].Maxu].w > e[e[u].Maxu].w) e[u].Maxu = e[e[u].ch[0]].Maxu;

	if (e[u].ch[1] && e[e[e[u].ch[1]].Maxu].w > e[e[u].Maxu].w) e[u].Maxu = e[e[u].ch[1]].Maxu;

}

inline void pd(int u){

	if (e[u].rev){

		swap(e[u].ch[0],e[u].ch[1]);

		e[e[u].ch[0]].rev ^= 1;

		e[e[u].ch[1]].rev ^= 1;

		e[u].rev = 0;

	}

}

inline void push_down(int u){

	int i = 0;

	do {temp[++i] = u;} while(!isrt(u) && (u = e[u].f));

	while (i) pd(temp[i--]);

}

inline int Find(int u){

	while (e[u].f) u = e[u].f;

	return u;

}

inline void spin(int u){

	int s = isr(u),fa = e[u].f;

	e[u].f = e[fa].f;

	if (!isrt(fa)) e[e[fa].f].ch[isr(fa)] = u;

	e[fa].ch[s] = e[u].ch[s^1];

	if (e[u].ch[s^1]) e[e[u].ch[s^1]].f = fa;

	e[fa].f = u;

	e[u].ch[s^1] = fa;

	push_up(fa);

}

inline void splay(int u){

	push_down(u);

	while(!isrt(u)){

		if (isrt(e[u].f)) spin(u);

		else if (isr(u) ^ isr(e[u].f)) spin(u),spin(u);

		else spin(e[u].f),spin(u);

	}

	push_up(u);

}

inline void Access(int u){

	for (int v = 0; u; u = e[v = u].f){

		splay(u);

		e[u].ch[1] = v;

		if (v) e[v].f = u;

		push_up(u);

	}

}

inline void Make_root(int u){

	Access(u); splay(u);

	e[u].rev ^= 1;

}

inline void Link(int u,int v){

	Make_root(u); e[u].f = v;

}

inline void Cut(int u,int v){

	Make_root(u); Access(v); splay(v);

	e[u].f = 0;

	e[v].ch[0] = 0;

	push_up(v);

}

inline int Query(int u,int v){

	if (Find(u) != Find(v)) return 0;

	Make_root(u); Access(v); splay(v);

	return e[v].Maxu;

}

void init(){

	e[0].w = INF;

	e[0].Maxu = 0;

	N = read();

	M = read();

	for (int i = 1; i <= M + N; i++) e[i].Maxu = i;

	for (int i = 1; i <= M; i++){

		edge[i].x = read();

		edge[i].y = read();

		edge[i].a = read();

		edge[i].b = read();

	}

	sort(edge + 1,edge + 1 + M);

}

void solve(){

	int ans = INF,x,y,t;

	for (int i = 1; i <= M; i++){

		e[N + i].w = edge[i].b;

		if (Find(x = edge[i].x) != Find(y = edge[i].y)){

			Link(N + i,x);

			Link(N + i,y);

		}else {

			t = Query(x,y);

			if(e[t].w > e[N + i].w){

				Cut(t,edge[t - N].x);

				Cut(t,edge[t - N].y);

				Link(N + i,x);

				Link(N + i,y);

			}

		}

		ans = min(ans,edge[i].a + e[Query(1,N)].w);

	}

	if (ans == INF) printf("-1\n");

	else printf("%d\n",ans);

}

int main()

{

	init();

	solve();

	return 0;

}