在 O(n) 的时间复杂度内求点权图上生成树

· · 休闲·娱乐

\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 都被加入到生成树的权值中。因此，生成树的权值总是与图中所有点的权值之和相等。

代码实现

#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++)，易得：

for(int i=1;i<=n;i++) {
    cin>>w[i];//输入个点点权
    sum+=w[i];//累加
}

可以发现 w[i] 只在上面的 for 循环中使用过，其他地方都没用过，所以可以不用 w 数组，输入时用一个变量来存：

int w;//点权
for(int i=1;i<=n;i++) {
    cin>>w;//输入个点点权
    sum+=w;//累加
}

代入原代码：

#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

分析

rt，题目可以抽象为求一个点数为2的点权图。

代码实现

#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记录

2、U535152 『LIO1-A』于困境中坚守希望

致谢

@upb_ & his blog（作者）

@LEMON_dasiy（格式修改）

参考文献

  1. 在 O(n) 的时间复杂度内求点权图上生成树 作者：@upb_

后记

创建时间（@upb_）：2024 年 12 月 30 日 20 时 20 分于机房（唐望同学生日过 68 天）

修改时间（格式）（@LEMON_dasiy）2025 年 1 月 2 日 19 时 30 分于机房（唐望同学生日过 71 天）

修改时间（增加优化、谷友评论）（@upb_）：2025 年 1 月 3 日 17 时 40 分于机房（唐望同学生日过 72 天）

修改时间（修修补补）（@upb_）：2025 年 1 月 3 日 19 时 9 分于机房（唐望同学生日过 72 天）

修改时间（增加应用）（@upb_）：2025 年 1 月 31 日 23 时 54 分于贵阳（唐望同学生日过 ?? 天）

想投“全站推荐/休闲·娱乐”，不知过不过得了

谷友评论

  1. Q：LG086 回复于 20 小时前 真是让人眼前一黑茅厕顿开！！！
    A：开了暗色插件？？？
  2. Q： Eden_star 回复于 8 分钟前 所以合并同类项后为什么w还是数组
    A：已修改。

    Copilot 锐评

    • 核心突破：边无效，点是唯一主角，点权总和即为树权。
    • 风格点评：幽默讽刺，颠覆图论传统，边缘化边的地位。
    • 技术亮点：
      • 极简实现，代码干净利落。
      • 高阶抽象，点集代替图结构。
      • 思维跳脱，定义重构，挑战常规。