BZOJ3669 膜法森林 - LCT

2024-02-24 03:20
文章标签 森林 lct bzoj3669 膜法

本文主要是介绍BZOJ3669 膜法森林 - LCT,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Solution

非常妙的排序啊。。。

仔细想想好像确实能够找出最优解QUQ

先对第一关键字排序, 在$LCT$ 维护第二关键字的最大值 所在的边。

添边时如果$u, v$ 不连通 就直接加边。  如果连通 并且路径上的最大值 大于 当前边 的 第二关键字, 那么可以换掉。

如果 $1$ 和 $N$ 连通 就 更新答案。

 

这样就可以保证 在 所有路径上的边 第一关键字 小于等于 当前边 的第一关键字的前提下, 第二关键字的 最大值  最小。

除了这一点不一样, 其他就是模板了。

 

Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define rd read()
  5 using namespace std;
  6 
  7 const int N = 1e5 + 5;
  8 const int inf = ~0U >> 2;
  9 
 10 int n, m;
 11 int ans = inf;
 12 
 13 struct edge {
 14     int u, v, a, b;
 15 }e[N << 1];
 16 
 17 int read() {
 18     int X = 0, p = 1; char c = getchar();
 19     for (; c > '9' || c < '0'; c = getchar())
 20         if (c == '-') p = -1;
 21     for (; c >= '0' && c <= '9'; c = getchar())
 22         X = X * 10 + c - '0';
 23     return X * p;
 24 }
 25 
 26 int cmp(const edge &A, const edge &B) {
 27     return A.a < B.a;
 28 }
 29 
 30 void cmin(int &A, int B) {
 31     if (A > B)
 32         A = B;
 33 }
 34 
 35 namespace LCT {
 36     int val[N << 1], f[N << 1], ch[N << 1][2], mx[N << 1], tun[N << 1];
 37 #define lc(x) ch[x][0]
 38 #define rc(x) ch[x][1]
 39 
 40     int isroot(int x) {
 41         return lc(f[x]) != x && rc(f[x]) != x;
 42     }
 43 
 44     int get(int x) {
 45         return rc(f[x]) == x;
 46     }
 47 
 48     void up(int x) {
 49         mx[x] = val[x];
 50         if (e[mx[lc(x)]].b > e[mx[x]].b) mx[x] = mx[lc(x)];
 51         if (e[mx[rc(x)]].b > e[mx[x]].b) mx[x] = mx[rc(x)];
 52     }
 53 
 54     void rev(int x) {
 55         swap(lc(x), rc(x));
 56         tun[x] ^= 1;
 57     }
 58 
 59     void pushdown(int x) {
 60         if (tun[x]) {
 61             if (lc(x)) rev(lc(x));
 62             if (rc(x)) rev(rc(x));
 63             tun[x] = 0;
 64         }
 65     }
 66 
 67 int st[N << 1], tp;
 68 
 69     void pd(int x) {
 70         while (!isroot(x)) {
 71             st[++tp] = x;
 72             x = f[x];
 73         }
 74         pushdown(x);
 75         while (tp) pushdown(st[tp--]);
 76     }
 77 
 78     void rotate(int x) {
 79         int old = f[x], oldf = f[old], son = ch[x][get(x) ^ 1];
 80         if (!isroot(old)) ch[oldf][get(old)] = x;
 81         ch[x][get(x) ^ 1] = old;
 82         ch[old][get(x)] = son;
 83         f[old] = x; f[son] = old; f[x] = oldf;
 84         up(old); up(x);
 85     }
 86 
 87     void splay(int x) {
 88         pd(x);
 89         for (; !isroot(x); rotate(x)) 
 90             if (!isroot(f[x]))
 91                 rotate(get(f[x]) == get(x) ? f[x] : x);
 92     }
 93 
 94     void access(int x) {
 95         for (int y = 0; x; y = x, x = f[x])
 96             splay(x), ch[x][1] = y, up(x);
 97     }
 98 
 99     void mroot(int x) {
100         access(x); splay(x); rev(x);
101     }
102 
103     void split(int x, int y) {
104         mroot(x); access(y); splay(y);
105     }
106 
107     int findr(int x) {
108         access(x); splay(x);
109         while(lc(x)) pushdown(x), x = lc(x);
110         return x;
111     }
112 
113     void link(int x, int y) {
114         mroot(x); f[x] = y;
115     }
116 
117     void cut(int x, int y) {
118         split(x, y);
119         f[x] = ch[y][0] = 0;
120     }
121 }
122 using namespace LCT;
123 
124 int main()
125 {
126     n = rd; m = rd;
127     for (int i = 1; i <= m; ++i) {
128         e[i].u = rd; e[i].v = rd;
129         e[i].a = rd; e[i].b = rd;
130     }
131     sort(e + 1, e + 1 + m, cmp);
132     for (int i = 1; i <= m; ++i)
133         val[i + n] = i;
134     for (int i = 1; i <= m; ++i) {
135         int x = e[i].u, y = e[i].v, t;
136         if (x == y) continue;
137         mroot(x);
138         if (findr(y) != x)
139             link(i + n, x), link(i + n, y);
140         else if (e[t = mx[y]].b > e[i].b)
141             cut(t + n, e[t].u), cut(t + n, e[t].v),
142             link(i + n, x), link(i + n, y);
143         mroot(1);
144         if (findr(n) == 1)
145             cmin(ans, e[i].a + e[mx[n]].b);
146     }
147     printf("%d\n", ans == inf ? -1 : ans);
148 }
View Code

 

转载于:https://www.cnblogs.com/cychester/p/9696513.html

这篇关于BZOJ3669 膜法森林 - LCT的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/740799

相关文章

【异常点检测 孤立森林算法】10分钟带你了解下孤立森林算法

孤立森林(isolation Forest)算法,2008年由刘飞、周志华等提出,算法不借助类似距离、密度等指标去描述样本与其他样本的差异,而是直接去刻画所谓的疏离程度(isolation),因此该算法简单、高效,在工业界应用较多。 用一个例子来说明孤立森林的思想:假设现在有一组一维数据(如下图),我们要对这组数据进行切分,目的是把点A和 B单独切分出来,先在最大,值和最小值之间随机选择一个值

数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解

本文逻辑: 本文由二叉树的遍历起手,讲解了二叉树的三种遍历方式,以及如何构造一颗二叉树,并在此基础上,扩展了更好的二叉树-线索二叉树。树和森林的存储结构讲解中,重点就是将树与森林转换为二叉树,这样二叉树的手段就能使用到树与森林当中。最后,讲解了二叉树与森林的遍历。 文章目录 1.二叉树的遍历1.1 二叉树的前,中,后序遍历1.2 二叉树的层次遍历1.3构造二叉树 2.线索二叉树2.1

随机森林的知识博客:原理与应用

随机森林(Random Forest)是一种基于决策树的集成学习算法,它通过组合多棵决策树的预测结果来提升模型的准确性和稳健性。随机森林具有强大的分类和回归能力,广泛应用于各种机器学习任务。本文将详细介绍随机森林的原理、构建方法及其在实际中的应用。 1. 随机森林的原理 1.1 集成学习(Ensemble Learning) 在机器学习中,集成学习是一种通过结合多个模型的结果来提高预测性能的

【机器学习】梯度提升和随机森林的概念、两者在python中的实例以及梯度提升和随机森林的区别

引言 梯度提升(Gradient Boosting)是一种强大的机器学习技术,它通过迭代地训练决策树来最小化损失函数,以提高模型的预测性能 随机森林(Random Forest)是一种基于树的集成学习算法,它通过组合多个决策树来提高预测的准确性和稳定性 文章目录 引言一、梯度提升1.1 基本原理1.1.1 初始化模型1.1.2 迭代优化1.1.3 梯度计算1.1.4模型更新 1.2

【HDU】5333 Undirected Graph【LCT+BIT】

传送门:【HDU】5333 Undirected Graph my  code: my~~code: #pragma comment(linker, "/STACK:1024000000")#include <stdio.h>#include <string.h>#include <map>#include <algorithm>using namespace std ;typed

mllib之随机森林与梯度提升树

随机森林和GBTs都是集成学习算法,它们通过集成多棵决策树来实现强分类器。 集成学习方法就是基于其他的机器学习算法,并把它们有效的组合起来的一种机器学习算法。组合产生的算法相比其中任何一种算法模型更强大、准确。 随机森林和梯度提升树(GBTs)。两者之间主要差别在于每棵树训练的顺序。 随机森林通过对数据随机采样来单独训练每一棵树。这种随机性也使得模型相对于单决策树更健壮,且不易在

机器学习项目——基于机器学习(决策树 随机森林 朴素贝叶斯 SVM KNN XGBoost)的帕金森脑电特征识别研究(代码/报告材料)

完整的论文代码见文章末尾 以下为核心内容和部分结果 问题背景 帕金森病(Parkinson’s Disease, PD)是一种常见的神经退行性疾病,其主要特征是中枢神经系统的多巴胺能神经元逐渐丧失,导致患者出现运动障碍、震颤、僵硬等症状。然而,除运动症状外,帕金森病患者还常常伴有一系列非运动症状,其中睡眠障碍是最为显著的非运动症状之一。 脑电图(Electroencephalogram, E

P4842 城市旅行(拆贡献 + LCT)

https://www.luogu.com.cn/problem/P4842 发现题目就是要维护一个LCT,然后我们只要把pushup写成功了就行。 那我们现在就不管LCT了,就单纯想用一棵二叉查找树怎么维护。分母是好搞的,分子我们要想点办法。 考虑右子树对左子树的贡献,我们假设处理出一个 L [ k ] L[k] L[k] 表示左子树中每个值乘以左边界的可选数量,我们现在再乘上右子树的大

5.4树,森林

5.4.1树的存储结构 可采用顺序存储结构or链式存储结构 要求能唯一的反映树中各节点之间的逻辑 1.双亲表示法 采用一端连续的空间来存储,同时在每个节点中增设一个伪指针,指示双亲节点在数组中的下标 优点:找双亲节点方便,找孩子不方便 attention:由于根节点无双亲节点,所以其双亲节点的坐标为-1; 双亲表示法的存储结构代码如下: #include<stdio.h>;#

5.sklearn-朴素贝叶斯算法、决策树、随机森林

文章目录 环境配置(必看)头文件引用1.朴素贝叶斯算法代码运行结果优缺点 2.决策树代码运行结果决策树可视化图片优缺点 3.随机森林代码RandomForestClassifier()运行结果总结 环境配置(必看) Anaconda-创建虚拟环境的手把手教程相关环境配置看此篇文章,本专栏深度学习相关的版本和配置,均按照此篇文章进行安装。 头文件引用 from sklear