✅ 春招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线200+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

京东-2026.03.21-第三套

这套目前只有一道图论题，但题型非常标准。题面表面是在“已有通道 + 候选新通道”里做规划，落地时要先把免费边缩成若干连通块，随后对候选边跑一遍 Kruskal。

题目一：星港联通计划

如果直接把已有通道和候选通道混在一起想，很容易绕进“怎么选组合”的细节里。更直接的切入点是：已有通道先并进并查集，后面只需要在连通块之间补最便宜的边，这就是最小生成树的原型。

难度：中等

01. 星港联通计划

问题描述

小柯正在维护一张由空中补给站组成的星港网络。

现在一共有 个星港，已经稳定运行的连接通道有 条。除此之外，工程组还给出了 条候选新通道，每条候选方案都有一个建造成本。

你需要从这 条候选新通道里选出若干条进行建造，使得所有星港最终都能互相连通，并且总代价最小。

输入格式

第一行输入三个整数 、、，分别表示星港数量、已开通通道数量和候选新通道数量。

接下来 行，每行输入两个整数 、，表示星港 和星港 之间已经有一条稳定通道。

再接下来 行，每行输入三个整数 、、，表示修建星港 和星港 之间的新通道需要成本 。

输出格式

输出一个整数，表示让所有星港连通所需的最小总代价。

样例输入

4 1 4
1 2
2 3 5
3 4 2
1 4 10
2 4 4

样例输出

6

样例说明

星港 和星港 原本已经连通。再修建：

• ，成本为
• ，成本为

就能让四个星港全部连通，总成本是 ，这是最优方案。

数据范围

题解

这题的核心不在“选哪些新航线”，而在于先把原本已经连通的部分缩成若干个连通块。

一旦这么看，后面的目标就很清楚了：

• 已有航线免费使用；
• 候选新航线按成本付费；
• 只要把这些连通块用最小代价连成一个整体。

这就是标准的最小生成树模型，直接用 Kruskal 即可。

第一步：先把已有航线合并掉

题目里给的 条已开通航线不需要额外花钱，所以它们本质上就是“已经存在的边”。

我们先开一个并查集，把这些边对应的端点全部合并：

• 如果 和 之间原本就有航线，就说明它们已经在同一个连通区域里。
• 这一阶段只做合并，不累计成本。

处理完以后，整张图会被分成若干个初始连通块。

第二步：对候选新航线做 Kruskal

把所有候选新航线按成本从小到大排序。

然后依次枚举每一条边：

• 如果这条边的两个端点已经在同一个连通块里，说明它只会形成环，跳过。
• 如果不在同一个连通块里，就把它加入答案，并把两个连通块合并。

因为我们始终优先拿当前能连接两个不同连通块的最小成本边，所以这正是 Kruskal 的贪心过程。

为什么这样一定最优

已有航线已经把图压成了若干个免费连通块。剩下要做的，只是用候选边把这些块接起来。

而在任意一步里，如果两块还没连通，Kruskal 选择的是当前能连接它们的最便宜边。根据最小生成树的切分性质：

• 在某个割上，权值最小的可选边一定可以出现在某一棵最小生成树里。

所以把候选边按成本从小到大尝试、只在两端还没连通时使用，最后得到的总代价就是最小值。

复杂度分析

设候选新航线数量为 。

• 排序复杂度：
• 并查集合并与查询复杂度：
• 总时间复杂度：
• 空间复杂度：

参考代码

• Python

import sys

input = lambda: sys.stdin.readline().strip()


class DSU:
    def __init__(self, n):
        self.fa = list(range(n + 1))

    def find(self, x):
        while self.fa[x] != x:
            self.fa[x] = self.fa[self.fa[x]]
            x = self.fa[x]
        return x

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx == fy:
            return False
        self.fa[fx] = fy
        return True


def solve():
    n, m, k = map(int, input().split())
    dsu = DSU(n)

    # 先合并已经开通的免费航线。
    for _ in range(m):
        a, b = map(int, input().split())
        dsu.union(a, b)

    edges = []
    for _ in range(k):
        a, b, v = map(int, input().split())
        edges.append((v, a, b))

    edges.sort()
    ans = 0

    # 再按成本从小到大补边。
    for v, a, b in edges:
        if dsu.union(a, b):
            ans += v

    root = dsu.find(1)
    for i in range(2, n + 1):
        if dsu.find(i) != root:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    solve()

• Cpp

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> fa;

    explicit DSU(int n) : fa(n + 1) {
        iota(fa.begin(), fa.end(), 0);
    }

    int find(int x) {
        if (fa[x] == x) {
            return x;
        }
        return fa[x] = find(fa[x]);
    }

    bo