题解 P4234 【最小差值生成树】

· · 题解

首先要先想明白怎么用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;
}