专栏文章
在 O(n) 的时间复杂度内求点权图上生成树
休闲·娱乐参与者 10已保存评论 10
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @miqlofg4
- 此快照首次捕获于
- 2025/12/04 06:50 3 个月前
- 此快照最后确认于
- 2025/12/04 06:50 3 个月前
\large\mathbf{upb}$$
关键词：Eilotik，点权图，生成树。
# 前言 & 摘要
这是有用的废话。
本文介绍一种在 $O(n)$ 的时间复杂度内求**点权图**上生成树（最大 or 最小）的方法。
# 引入
## 生成树是什么
### 概念
生成树是图论中的一个基本概念，它指的是在一个**连通图**中，包含图中**所有顶点**且形成**树**结构的**子图**。在处理生成树问题时，最常见的是寻找最小生成树，即边权总和最小的生成树。
# 定理
1. 在一个边数为 $m$ 的生成树中，会有 $m$ 条边。
2. 在一个由一个点数为 $n$ 的图所构成的生成树中有 $n$ 个点，会有 $n-1$ 条边。
3. 原图的点集等于新生成树的点集。
# 算法(仅点权图)
## Eilotik 算法
### 证明过程
假设原图是一个图，包含 $V$ 个顶点和 $E$ 条边。每个顶点具有一个权值 $w_i$。生成树是该图的一个子图，包含所有顶点且是连通的。
生成树的权值是该树中所有点的权值之和：
W(T) = \sum_{i \in V} w_i
其中 $W(T)$ 是生成树的权值，$V$ 是图的点集。
在构建生成树时，我们不需要关心选择哪些边，只需要关心哪些顶点包含在内。因为生成树中的每个顶点都必须包含，而每个顶点的权值 $w_i$ 都被加入到生成树的权值中。因此，**生成树的权值总是与图中所有点的权值之和相等。**
### 代码实现
```cpp
#include <bits/stdc++.h>//万能头
using namespace std;//使用命名空间，这样后在cin/cout等前不用加std::等
const int N=114515;//最大点数
int w[N]/*原图点权*/,sum/*生成树的总点权*/=0,n/*点数*/;
int main(){//主函数
cin>>n;//输入点数
for(int i=1;i<=n;i++) cin>>w[i];//输入个点点权
for(int i=1;i<=n;i++) sum+=w[i];//累加
cout<<sum;//输出
return 0;//结束
}
```
### 优化
让我们观察一下`for(int i=1;i<=n;i++) cin>>w[i];//输入个点点权`和`for(int i=1;i<=n;i++) sum+=w[i];//累加`。合并同类项`for(int i=1;i<=n;i++)`，易得：
```cpp
for(int i=1;i<=n;i++) {
cin>>w[i];//输入个点点权
sum+=w[i];//累加
}
```
可以发现 `w[i]` 只在上面的 for 循环中使用过，其他地方都没用过，所以可以不用 `w` 数组，输入时用一个变量来存：
```cpp
int w;//点权
for(int i=1;i<=n;i++) {
cin>>w;//输入个点点权
sum+=w;//累加
}
```
代入原代码：
```cpp
#include <bits/stdc++.h>//万能头
using namespace std;//使用命名空间，这样后在cin/cout等前不用加std::等
const int N=114515;//最大点数
int sum/*生成树的总点权*/=0,n/*点数*/;
int main(){//主函数
cin>>n;//输入点数
int w;//点权
for(int i=1;i<=n;i++) {
cin>>w;//输入个点点权
sum+=w;//累加
}
cout<<sum;//输出
return 0;//结束
}
```
这样，我们可以在输入时处理，将原代码的时间降低近一半。
### 注意
LLG is `priority_queue<item>` ;
# 复杂度分析
我们使用了 for 循环，在 $O(n)$ 的时间复杂度内求点权图上生成树。
# 应用
## 1、[P1001 A+B Problem](https://www.luogu.com.cn/problem/P1001)
### 分析
rt，题目可以抽象为求一个**点数为2的点权图**。
### 代码实现
```cpp
#include <bits/stdc++.h>//万能头
using namespace std;//使用命名空间，这样后在cin/cout等前不用加std::等
const int N=114515;//最大点数
int sum/*生成树的总点权*/=0,n/*点数*/=2;
int main(){//主函数
//cin>>n;不用输入n了
int w;//点权
for(int i=1;i<=n;i++) {
cin>>w;//输入个点点权
sum+=w;//累加
}
cout<<sum;//输出
return 0;//结束
}
```
### [AC记录](https://www.luogu.com.cn/record/200961987)
## 2、[U535152 『LIO1-A』于困境中坚守希望](https://www.luogu.com.cn/article/pkjwzd1q)
# 致谢
@[upb_](luogu://user/1344304) & [his blog](http://upb.tttttttttt.top/)（作者）
@[LEMON_dasiy](luogu://user/974708)（格式修改）
# 参考文献
1. [在 O(n) 的时间复杂度内求点权图上生成树](https://www.luogu.com.cn/article/1tqdgqk8) 作者：@[upb_](luogu://user/1344304)
# 后记
创建时间（@[upb_](luogu://user/1344304)）：2024 年 12 月 30 日 20 时 20 分于机房（唐望同学生日过 68 天）
修改时间（格式）（@[LEMON_dasiy](luogu://user/974708)）2025 年 1 月 2 日 19 时 30 分于机房（唐望同学生日过 71 天）
修改时间（增加优化、谷友评论）（@[upb_](luogu://user/1344304)）：2025 年 1 月 3 日 17 时 40 分于机房（唐望同学生日过 72 天）
修改时间（修修补补）（@[upb_](luogu://user/1344304)）：2025 年 1 月 3 日 19 时 9 分于机房（唐望同学生日过 72 天）
修改时间（增加应用）（@[upb_](luogu://user/1344304)）：2025 年 1 月 31 日 23 时 54 分于贵阳（唐望同学生日过 ?? 天）
###### ~~想投“全站推荐/休闲·娱乐”~~，不知过不过得了
## 谷友评论
1. Q：LG086 回复于 20 小时前 真是让人眼前一黑茅厕顿开！！！
A：开了暗色插件？？？
2. Q：
Eden_star 回复于 8 分钟前 所以合并同类项后为什么w还是数组
A：已修改。
## Copilot 锐评
>- 核心突破：边无效，点是唯一主角，点权总和即为树权。
>- 风格点评：幽默讽刺，颠覆图论传统，边缘化边的地位。
>- 技术亮点：
> - 极简实现，代码干净利落。
> - 高阶抽象，点集代替图结构。
> - 思维跳脱，定义重构，挑战常规。相关推荐
评论
共 10 条评论，欢迎与作者交流。
正在加载评论...