自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

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

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

以下是正文

首先要先想明白怎么用$LCT$求最小生成树

于是我又不要脸$QWQ$的推荐了

然后我们考虑这道题怎么做

要保证边权差最小，不妨假设当前边权为$k$，则此时我们需要最小边权最大。

所以可以按照边权排序。

类似于求最小生成树的方法，我们每次加边后都需要判一下连通性，如果联通就减去边权中最小值。

至于如何求出所有边权中的最小值，因为已经排序，所以有下标小的点其点权一定小。

所以我们可以用 $book$ 数组来标记那些点已经被标记，然后类似与队列的一个一个弹$?$

当然，需要统计答案的时候，还要判断$Id_{num}$（合并次数）（当前联通块数量是否为1）是否为$n-1$

区别与最小生成树的模板，因为我们有编号小的点且为边的点其越小，所以我们可以这样写$pushup(x)$

void pushup( int x ) {
	t[x].id = x;
	if( t[ls(x)].id > n && ( t[x].id <= n || t[x].id > t[ls(x)].id ) ) t[x].id = t[ls(x)].id;
	if( t[rs(x)].id > n && ( t[x].id <= n || t[x].id > t[rs(x)].id ) ) t[x].id = t[rs(x)].id; 
    //如果当前的点为点点，而儿子有边点，则复制儿子
    //如果当前点位边点，但编号大于儿子，也复制儿子
}

其他部分与最小生成树做法异斧同工

#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 ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define inf 99999999
const int M = 200000 + 5;
const int N = 50000 + 5;
struct E{
	int from, to, w;
}e[M * 2];
struct LCT {
	int son[2], fa, id;
	bool mark;
}t[2 * M];
int ans, Idnum, Idnex, st[M * 2], book[2 * N], n;
bool cmp( E x, E y ) {
	return x.w < y.w;
}
bool isroot( int x ) {
	return ( ls(t[x].fa) != x ) && ( rs(t[x].fa) != x );
}
void pushup( int x ) {
	t[x].id = x;
	if( t[ls(x)].id > n && ( t[x].id <= n || t[x].id > t[ls(x)].id ) ) t[x].id = t[ls(x)].id;
	if( t[rs(x)].id > n && ( t[x].id <= n || t[x].id > t[rs(x)].id ) ) t[x].id = t[rs(x)].id;
}
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 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[t[x].son[qwq ^ 1]].fa = f, t[f].son[qwq] = t[x].son[qwq ^ 1];
	t[f].fa = x, t[x].son[qwq ^ 1] = f;
	pushup(f), pushup(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 );
}
bool check( int x, int y ) {
	makeroot( x );
	return findroot(y) != x;
}
void link( int x, int y ) {
	makeroot( x );
	t[x].fa = y;
} 
signed main()
{
	n = read(); int m = read(), ll = 0, x, y, now;
	
	rep( i, 1, m )  e[i].from = read(), e[i].to = read(), e[i].w = read();
	sort( e + 1, e + m + 1, cmp );
	
	Idnex = n, ll = 1, ans = inf;
	
	rep( i, 1, m ) {
		++Idnex;
		x = e[i].from, y = e[i].to;
		if( e[i].to == e[i].from ) { book[i] = 1; continue; }
		
		if( check( e[i].from, e[i].to ) )
			link( e[i].from, Idnex ), link( Idnex, e[i].to ), ++ Idnum;
		else {
			split( x, y ), now = t[y].id;
			book[now - n] = 1, Splay( now );
			t[ls(now)].fa = t[rs(now)].fa = 0;
			link( x, Idnex ), link( Idnex, y );
		}
		while( book[ll] && ll <= i ) ++ ll; 
		if( Idnum >= n - 1 ) ans = min( ans, e[i].w - e[ll].w );
	}
	printf("%d\n", ans);
	return 0;
}