本文主要是介绍[BZOJ3669][Noi2014]魔法森林 LCT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题有两个权值 我们把所有边按权值a排序 剩下的边都看成点放进一个LCT中 维护每一节点的最大权值点的位置 枚举所有的边 如果u, v连通 则删去最大的边 加入这条边
否则直接加入这条边 当发现1和n连通的时候更新答案
开数组的时候把val 和 MAX开成bool也是醉了orz
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define SF scanf
#define PF printf
using namespace std;
typedef long long LL;
const int MAXN = 50000;
const int MAXM = 100000;
const int MAXNODE = 150000;
const int INF = 1234567890;
struct LCT {int ch[MAXNODE+10][2], fa[MAXNODE+10], MAX[MAXNODE+10];int val[MAXNODE+10], Q[MAXNODE+10]; bool rev[MAXNODE+10];bool isroot(int x) {return ch[fa[x]][0] != x && ch[fa[x]][1] != x;}void up(int x) {int ls = ch[x][0], rs = ch[x][1];MAX[x] = x;if(val[MAX[ls]] > val[MAX[x]]) MAX[x] = MAX[ls];if(val[MAX[rs]] > val[MAX[x]]) MAX[x] = MAX[rs];}void pushdown(int x) {int &ls = ch[x][0], &rs = ch[x][1];if(rev[x]) {rev[x] ^= 1; rev[ls] ^= 1; rev[rs] ^= 1;swap(ls, rs);}}void Rotate(int x) {int y = fa[x], z = fa[y];bool d = x == ch[y][0];if(!isroot(y)) ch[z][y == ch[z][1]] = x;fa[x] = z; fa[y] = x; fa[ch[x][d]] = y;ch[y][!d] = ch[x][d]; ch[x][d] = y;up(y);}void splay(int x) {int top = 0; Q[++top] = x;for(int i = x; !isroot(i); i = fa[i]) Q[++top] = fa[i];for(int i = top; i; i--) pushdown(Q[i]);while(!isroot(x)) {int y = fa[x];if(!isroot(y)) Rotate((ch[y][0] == x ^ ch[fa[y]][0] == y) ? x : y);Rotate(x);}up(x);}void access(int x) {int t = 0;while(x) {splay(x);ch[x][1] = t;t = x; x = fa[x];}}void makeroot(int x) {access(x); splay(x); rev[x] ^= 1;}void link(int x, int y) {makeroot(x); fa[x] = y; }void cut(int x, int y) {makeroot(x); access(y); splay(y); ch[y][0] = fa[x] = 0;}int query(int x, int y) {makeroot(x); access(y); splay(y); return MAX[y];}
} sp;
int fa[MAXNODE+10], n, m, ans = INF;
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);
}
struct Node {int u, v, a, b;bool operator < (const Node &t) const {return a < t.a;}
} E[MAXM+10];
int main() {SF("%d%d", &n, &m);for(int i = 1; i <= n; i++) fa[i] = i;for(int i = 1; i <= m; i++) SF("%d%d%d%d", &E[i].u, &E[i].v, &E[i].a, &E[i].b);sort(E+1, E+1+m);for(int i = 1; i <= m; i++) {sp.val[n+i] = E[i].b;sp.MAX[n+i] = n+i;}for(int i = 1; i <= m; i++) {int u = E[i].u, v = E[i].v, wt = E[i].b;int x = find(u), y = find(v);if(x != y) {fa[x] = y;sp.link(u, n+i); sp.link(v, n+i);}else {int t = sp.query(u, v);if(wt < sp.val[t]) {sp.cut(E[t-n].u, t); sp.cut(E[t-n].v, t);sp.link(u, n+i); sp.link(v, n+i);}}if(find(1) == find(n)) ans = min(ans, sp.val[sp.query(1, n)] + E[i].a);}PF("%d", ans == INF ? -1 : ans);
}这篇关于[BZOJ3669][Noi2014]魔法森林 LCT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
