自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 21:37:08，当前版本为作者最后更新于2019-03-22 15:21:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感觉最近做的一些$LCT$的题目其实都是不断加边，判环，取较优者。

比如这道题，一句话题解就是按照边权$A$排序后用$LCT$维护边权$B$的最小生成树

比如最小生成树，它用$LCT$实现的话主要就是遇到一条边后，若其联通了两个已经联通的点，那么其为返祖边，会形成环，那么我们就把环上最大的边断掉即可。

简单写就是$split(u,v)$，然后把$cut(max, u), cut(max,v)$

这道题也类似的，我们可以离线，将边按照边权$A$排序

然后不断的加边，如果一条边连接了两个联通块，那么这条路径是必需的。

这个时候我们保证了边权$A$单调递增，我们用$LCT$维护图中的边权$B$

然后对于一条路径，如果其沟通了两个已经联通的联通块，我们可以这样考虑：

当前路径的$A$比之前存在的任意路径的$A$都大，如果其$B$比这环上边$B$的最大值还要大，那么加入这条边只会让答案变得更不优。

如果当前路径的$B$比环上最大的$B$要小，那么加入这条路径后，显然有：

$(1):$假如当前$1-n$未联通，那么对于后续的边，若其加入后可以使$1-n$联通，不难想到：其$A$显然仍然大于当前边，所以我们需要最小化链上的$B$，也就是断掉环上最大$B$的边，然后加入这条边

$(2):$假如当前$1-n$已经联通，我们实际上已经求得了最大 A 比此边小的时候的答案，我们可以先加入此边，求出最大 A 稍微大一点的答案，取$min$，然后类似$(1)$的分析，可以发现这条边加入后会使得后续边算得的答案更优。

当然前提是这条边的$B$大于环上最大$B$

注意细节

#include<bits/stdc++.h>
using namespace std;
int read() {
	char cc = getchar(); int cn = 0, flus = 1;
	while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
	while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
	return cn * flus;
}
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
const int N =  150000 + 5; 
const int inf = 1234567890;
struct E {
	int from, to, a, b;
} e[N];
struct LCT {
	int son[2], fa, mx, id;
	bool mark;
} t[N];
int n, m, Idnum, ans, w[N], st[N];
bool cmp( E x, E y ) {
	return ( x.a == y.a ) ? x.b < y.b : x.a < y.a ;
}
bool isroot( int x ) {
	return ( ls(t[x].fa) != x ) && ( rs(t[x].fa) != x );
}
void pushup( int x ) {
	t[x].mx = w[x], t[x].id = x;
	if( ls(x) && t[ls(x)].mx > t[x].mx ) t[x].mx = t[ls(x)].mx, t[x].id = t[ls(x)].id;
	if( rs(x) && t[rs(x)].mx > t[x].mx ) t[x].mx = t[rs(x)].mx, t[x].id = t[rs(x)].id;
}
void rotate( int x ) {
	int f = t[x].fa, ff = t[f].fa, qwq = ( rs(f) == x );
	t[x].fa = ff;
	if( !isroot(f) ) t[ff].son[rs(ff) == f] = x;
	t[f].son[qwq] = t[x].son[qwq ^ 1], t[t[x].son[qwq ^ 1]].fa = f;
	t[x].son[qwq ^ 1] = f, t[f].fa = x;
	pushup(f), pushup(x);
}
void pushmark( int x ) {
	if( t[x].mark ) {
		t[x].mark = 0, t[ls(x)].mark ^= 1, t[rs(x)].mark ^= 1,
		swap( ls(x), rs(x) );
	}
} 
void Splay( int x ) {
	int top = 0, now = x; st[++top] = now;
	while( !isroot(now) ) st[++top] = ( now = t[now].fa );
	while( top ) pushmark( st[top--] );
	while( !isroot(x) ) {
		int f = t[x].fa, ff = t[f].fa;
		if( !isroot(f) ) ( ( rs(ff) == f ) ^ ( rs(f) == x ) ) ? rotate(x) : rotate(f) ;
		rotate(x);
	}
}
void access( int x ) {
	for( int y = 0; x; y = x, x = t[y].fa )
		Splay(x), t[x].son[1] = y, pushup(x);
}
void makeroot( int x ) {
	access(x), Splay(x), t[x].mark ^= 1, pushmark(x);
}
int findroot( int x ) {
	access(x), Splay(x), pushmark(x);
	while( ls(x) ) pushmark( x = ls(x) );
	return x;
}
void split( int x, int y ) {
	makeroot(x), access(y), Splay(y);
}
void link( int x, int y ) {
	makeroot(x);
	if( findroot(y) != x ) t[x].fa = y;
}
bool check( int x, int y ) {
	makeroot(x);
	return findroot(y) != x;
}
signed main()
{
	n = read(), m = read(), ans = inf;
	rep( i, 1, m ) e[i].from = read(), e[i].to = read(), e[i].a = read(), e[i].b = read();
	sort( e + 1, e + m + 1, cmp );
	rep( i, 1, m ) {
		w[i + n] = e[i].b;
		if( e[i].from == e[i].to ) continue;
		if( check( e[i].from, e[i].to ) ) link( e[i].from, i + n ), link( i + n, e[i].to );
		else {
			split( e[i].from, e[i].to );
			int now = t[e[i].to].id, maxb = t[e[i].to].mx;
			if( maxb <= e[i].b ) continue;
			Splay( now ), t[ls(now)].fa = t[rs(now)].fa = 0;
			link( e[i].from, i + n ), link( i + n, e[i].to );
		} 
		if( !check( 1, n ) ) {
			split( 1, n ); ans = min( ans, t[n].mx + e[i].a );
		}
	}
	if( ans == inf ) puts("-1");
	else printf("%d\n", ans);
	return 0;
}