#创作计划#最小生成树的构造及应用

userId_undefined
🥥
尊贵铂金

2026-04-18 19:00:06

发布于：上海

742阅读
0回复
0点赞

叠甲：没事干写一篇好玩，不喜勿喷，有问题欢迎指出，暂时已完结。

本文只讲Kruskal，我在vjudge拉了个比赛包含所有题目,A-R题为例题，S-Y为附加题。

前置知识：并查集，贪心，树的性质，请先行了解。

一、最小生成树的定义

生成树（spanning tree）：一个连通无向图的生成子图，同时要求是树．也即在图的边集中选择 𝑛−1𝑛 −1条，将所有顶点连通。我们定义无向连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。
FromFrom oi-wiki

二、Kruskal算法模板

Kruskal算法是一种贪心算法，非常好写，算法的思想是由边权从小到大遍历，只要两个节点还未联通，就把它们连上。维护连通性的问题，套用单次合并O(log⁡n)O(\log n) 或者 𝑂(α(𝑚))𝑂(\alpha(𝑚))的并查集即可。加上排序的O(mlog⁡m)O(m\log m)，Kruskal算法的总复杂度为O(mlog⁡m+mlog⁡n)O(m \log m + m \log n)。
贴上模板代码（即A题代码）

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x,y,z;
}a[200005];
bool cmp(node x,node y)
{
    return x.z<y.z;
}
int n,m,ans,cnt,fa[100005];
int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y)fa[x]=y;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(a[i].x)!=find(a[i].y))
        {
            ans+=a[i].z;
            cnt++;
            merge(a[i].x,a[i].y);
        }
    }
    if(cnt==n-1)cout<<ans;
    else cout<<"orz";
    return 0;
}

三、例题

B

这就是最大生成树的模板，排序规则改掉就行了。
Code

C

跑WW遍最小生成树，注意在输入时给每条边加一个第几周开放的参数，跑最小生成树时检测边的开放时间是否小于等于当前时间即可，这样就不用每周都排序了。
Code

D

假设能使用kk个卫星设备，就相当于让kk个点直接连通，在最小生成树中，一定会用k−1k-1条边。那么最优方案就一定是把原图中最长的k−1k-1条边的边权取消，只需输出最小生成树中第kk长的边即可。
Code

E

题目要求我们最大化任意两个部落之间的距离的最小值，实际上这个最小值就是在不同部落的任意两个居住点的最近距离。不难想到在部落内部尽量连较短的边，不让更短的边放在不同部落之间。因为要分为kk个部落，因此只需要n−kn-k条有用的边（遍历到这条边时两节点还未被联通的边）即可，所以直接输出第n−k+1n-k+1条有用边的长度即可。（就是连结两个部落的边中最短的）
Code

F

构造为图论问题，快速幂预处理连边，没了。
Code

G

在线算法不知道怎么办，考虑离线处理，把所有查询的边都放进去排序，跑最小生成树，跑的过程中如果是原本就有的边直接正常处理，如果是查询边，检测这条边是否有用（即两个点是否已联通），如果有用就把Yes放入答案，没有就放入No，注意查询之间相互独立，所以就算有用也千万不要加边。
Code

H

直接连边O(n2)O(n^2)指定炸，考虑删边，例如当xi≤xj≤xkx_i \leq x_j \leq x_k时，只需要连接ii与jj、jj与kk，而不需要连ii与kk。那么我们按x,yx,y分别排序后将相邻点连边即可。可以证明如果一条边是有效的，那么一定不会在按xx排序和按yy排序后都被鉴定为无效边。
Code

I

就是求在不用第一条边的情况下，第一条边的两个点联通的最小边权。跑第2−m2-m条边最小生成树过程中检测第一条边两个点的连通性即可，注意如果最终都无法联通,输出10910^9。
Code

J

首先买了第 II 样东西，再买第 JJ样的情况显然可以看做一条边权为KI,JK_{I,J}的边，那么直接买一样东西花费AA元的情况怎么办呢？这时候就可以引入一个超级源点，即00号点，这样就可以把这种情况构造为一条从00联向任意一点的边权为AA的边了。
Code

K

和J题几乎一模一样，挖水井就是向超级源点建边，修筑水道就是普通连边。
Code

L

不讲了，L≈\approxK，但是注意这是远古题目答案末尾一定要换行！！！我被这个坑了20分钟。
Code

M

笑点解析：

感谢PPL友情出演

接近正解的错误方法PPL已经给我们介绍过了，就是建两个超级源点分别代表港口与机场，然后暴力跑Kruskal，但是这样有个问题：我们的目标不是让包括超级源点在内的所有点联通，只是1−n1-n号点的联通，因此可能会出现无效连边（明明1−n1-n号点已经联通了还非要去连接超级源点）。
那么怎么办呢？注意到超级源点可以用也可以不用，那么枚举这两个超级源点的使用情况跑4遍Kruskal即可，注意可以给每条边一个编号，说明它属于机场边，港口边还是道路边，这样就不需要每次枚举使用情况都排序了。
那么为什么J、K、L没有这个问题呢？因为J、K、L题都必须使用超级源点，但是这道题就不一样了。
Code

N

先不考虑额外的MM条边，只看如何最小化生成树的ax+aya_x+a_y之和，显然最优方案是一个菊花图，即将所有点都直接连向axa_x最小的点。如果不考虑额外MM条边时，一条边不在最小生成树内，那么再加入MM条边后，也一定不需要考虑，所以只需要连上原始生成树的N−1N-1条边和额外的MM条边并跑Kruskal即可。
Code

O

不讲了，O≈\approxK，建边的公式不同，改一下就行了。
Code

P

看完前面的题，你会发现Road真不难
首先因为村庄数少，不难想到遍历所有村庄的修复状态跑2k2^k次最小生成树，时间复杂度O(2kmlogm)O(2^kmlogm)，48pts48pts，考虑优化。
根据N题的剪枝方法，在不考虑村庄的情况下不在最小生成树内的边，有了村庄就更不可能在最小生成树内了。那么就可以预处理跑一边Kruskal，将最小生成树内的边放入新的边集，可以大幅缩减边数(1.1×106→1.1×1051.1\times10^6\to1.1\times10^5)。
根据M题的方法对包含村庄边在内的所有边进行预编号和预排序，这样就不用排2k2^k次序了。
最终时间复杂度O(mlogm+2knklogn)O(mlogm+2^knklogn)，也可以加上启发式合并O(mlogm+2knkα(n))O(mlogm+2^knk\alpha(n))。
Code

Q

首先肯定是优先连载重限制较大的边最优，所以先将边权从大到小排序，然后用Kruskal重构树。它和普通的Kruskal有区别的一点是Kruskal重构树不是直接连边，而是创造一个虚拟节点，点权就是连接这条边的边权，让连接的两个点成为它的左右儿子，查询两个点路径的最小边权的最大值的问题就转化为查询两个点树上路径经过的虚拟节点的点权的最大值。不难发现这个问题就相当于求Kruskal 重构树上两点之间的 LCA 的权值。
Code

R

不讲了，R≈\approxQ，上题是最大生成树，这题是最小生成树，没了。
Code

大家觉得我有必要写S-Y吗（实际上除了S我一道都不会）

userId_undefined
去预览
0/2000

全部评论 80

热门讨论