当前位置：首页 > news >正文

[NOI2014] 魔法森林（LCT维护MST）

news 来源：原创 2024/9/19 10:02:01

https://www.luogu.com.cn/problem/P2387

考虑按 $a$ 排序加边，我们只需要维护 $1, n$ 的最短链就行

假如如果一直是森林那么是好做的，直接LCT即可。如果加入一条边后有环，我们可以尝试把环上最大一条边删掉。

实现的时候，我们可以把边换成点，然后把链提取出来，在平衡树内删掉最大点即可

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL#define debug(...) fprintf(stdout, ##__VA_ARGS__)#define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else#define debug(...) void(0)#define debag(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 200010
struct node {int u, v, a, b; 
}e[N]; 
int n, m, i, j, k, T;
int ans, a[N], u, v; namespace LCT {
#define ls(x) (son[x][0])
#define rs(x) (son[x][1])int son[N][2], rev[N], mx[N], fa[N]; void push_down(int x) {if(rev[x]) {swap(ls(x), rs(x)); if(ls(x)) rev[ls(x)] ^= 1; if(rs(x)) rev[rs(x)] ^= 1; rev[x] = 0; }}void push_up(int x) {mx[x] = x; if(a[mx[ls(x)]] > a[mx[x]]) mx[x] = mx[ls(x)]; if(a[mx[rs(x)]] > a[mx[x]]) mx[x] = mx[rs(x)]; }bool isRoot(int x) {if(!fa[x]) return true; return ls(fa[x]) != x && rs(fa[x]) != x; }int zh(int x) {return rs(fa[x]) == x; }void Rotate(int x) {int y = fa[x], z = fa[y]; int k = zh(x), w = son[x][k ^ 1]; if(z && !isRoot(y)) son[z][zh(y)] = x; if(w) fa[w] = y, son[y][k] = w; else son[y][k] = 0; fa[x] = z; fa[y] = x; son[x][k ^ 1] = y; push_up(y); push_up(x); push_up(z); }void Splay(int x) {stack<int>sta; sta.push(x); for(int y = x; !isRoot(y); y = fa[y]) sta.push(fa[y]); while(!sta.empty()) push_down(sta.top()), sta.pop(); while(!isRoot(x)) {int y = fa[x]; if(!isRoot(y)) {if(zh(y) == zh(x)) Rotate(y); else Rotate(x); }Rotate(x); }}void access(int x) {debug("access(%d)\n", x); for(int y = 0; x; y = x, x = fa[x]) {Splay(x); rs(x) = y; push_up(x); }}void makeRoot(int x) {access(x); Splay(x); rev[x] ^= 1; }int findRoot(int x) {access(x); Splay(x); while(push_down(x), ls(x)) x = ls(x); Splay(x); return x; }bool check(int x, int y) {makeRoot(x); return findRoot(y) == x; }void Link(int x, int y) {debug("Link(%d %d)\n", x, y); makeRoot(x); fa[x] = y; }void Delete(int x) {makeRoot(x); Splay(x); push_down(x); fa[ls(x)] = fa[rs(x)] = 0; ls(x) = rs(x) = 0; }int Qrymax(int x, int y) {makeRoot(x); access(y); Splay(y); int z = mx[y]; Splay(z); return z; }void print() {int i; #ifdef LOCALdebug("(%d %d %d | %d %d)\n", fa[1], ls(1), rs(1), a[1], mx[1]); for(i = 1; i <= n + m; ++i) if(fa[i] || ls(i) || rs(i)) debug("fa[%d] = %d(%d)(%d %d) || %d %d\n", i, fa[i], isRoot(i), ls(i), rs(i), a[i], mx[i]); debug("----------------------------------------\n"); #endif}
}signed main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}n = read(); m = read(); ans = 1e9; for(i = 1; i <= n + m; ++i) LCT :: mx[i] = i; for(i = 1; i <= m; ++i) {e[i].u = read(); e[i].v = read(); e[i].a = read(); e[i].b = read(); }sort(e + 1, e + m + 1, [] (node x, node y) { return x.a < y.a; }); for(i = 1; i <= m; ++i) {u = e[i].u; v = e[i].v; a[i + n] = e[i].b; debug("(%d %d) %d %d\n", u, v, e[i].a, e[i].b); if(!LCT :: check(u, v)) {
//			debug("Link(%d %d)\n", u, v); LCT :: Link(u, i + n);
//			LCT :: print(); LCT :: Link(v, i + n); }else {int x = LCT :: Qrymax(u, v); //pathif(a[x] > e[i].b) {LCT :: Delete(x); LCT :: Link(u, i + n), LCT :: Link(v, i + n); }}
//		LCT :: print(); if(LCT :: check(1, n)) {int x = LCT :: Qrymax(1, n); debug("#### %d + %d(%d)\n", e[i].a, a[x]); ans = min(ans, e[i].a + a[x]); }}printf("%d", ans == 1e9 ? -1 : ans); return 0;
}