感覺(jué)最近做的一些\(LCT\)的題目其實(shí)都是不斷加邊，判環(huán)，取較優(yōu)者。

比如這道題，一句話題解就是按照邊權(quán)\(A\)排序后用\(LCT\)維護(hù)邊權(quán)\(B\)的最小生成樹(shù)

比如最小生成樹(shù)，它用\(LCT\)實(shí)現(xiàn)的話主要就是遇到一條邊后，若其聯(lián)通了兩個(gè)已經(jīng)聯(lián)通的點(diǎn)，那么其為返祖邊，會(huì)形成環(huán)，那么我們就把環(huán)上最大的邊斷掉即可。

簡(jiǎn)單寫就是\(split(u,v)\)，然后把\(cut(max, u), cut(max,v)\)

這道題也類似的，我們可以離線，將邊按照邊權(quán)\(A\)排序

然后不斷的加邊，如果一條邊連接了兩個(gè)聯(lián)通塊，那么這條路徑是必需的。

這個(gè)時(shí)候我們保證了邊權(quán)\(A\)單調(diào)遞增，我們用\(LCT\)維護(hù)圖中的邊權(quán)\(B\)

然后對(duì)于一條路徑，如果其溝通了兩個(gè)已經(jīng)聯(lián)通的聯(lián)通塊，我們可以這樣考慮：

當(dāng)前路徑的\(A\)比之前存在的任意路徑的\(A\)都大，如果其\(B\)比這環(huán)上邊\(B\)的最大值還要大，那么加入這條邊只會(huì)讓答案變得更不優(yōu)。

如果當(dāng)前路徑的\(B\)比環(huán)上最大的\(B\)要小，那么加入這條路徑后，顯然有：

\((1):\)假如當(dāng)前\(1-n\)未聯(lián)通，那么對(duì)于后續(xù)的邊，若其加入后可以使\(1-n\)聯(lián)通，不難想到：其\(A\)顯然仍然大于當(dāng)前邊，所以我們需要最小化鏈上的\(B\)，也就是斷掉環(huán)上最大\(B\)的邊，然后加入這條邊

\((2):\)假如當(dāng)前\(1-n\)已經(jīng)聯(lián)通，我們實(shí)際上已經(jīng)求得了最大 A 比此邊小的時(shí)候的答案，我們可以先加入此邊，求出最大 A 稍微大一點(diǎn)的答案，取\(min\)，然后類似\((1)\)的分析，可以發(fā)現(xiàn)這條邊加入后會(huì)使得后續(xù)邊算得的答案更優(yōu)。

當(dāng)然前提是這條邊的\(B\)大于環(huán)上最大\(B\)

注意細(xì)節(jié)

#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; }

轉(zhuǎn)載于:https://www.cnblogs.com/Soulist/p/10586202.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的题解 P2387 【[NOI2014]魔法森林】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。