CSP Week6 Problem C Kruskal 最小生成树 + 超级源点 (Gym – 270437 H)

CSP-kruskal生成树+超级源点思想

文章结构概述

• CSP-kruskal生成树结合超级源点概念

  • • 相关知识简要说明

    • 题目内容概览

    • • 输入信息及示例输入
      • 输出结果及示例输出

    • 题目内容重新表述

    • 解题思路简述

    • 题目对应程序代码

相关知识简述

最小生成树作为图论中处理连通性问题的重要组成部分，其构造方法主要包含kruskal与prim两种。鉴于prim算法在实现过程中通常需要借助斐波那契堆或平衡树等复杂数据结构进行优化，实现难度较高，因此本文仅对kruskal算法的实现过程与核心思想进行阐述。
kruskal算法的核心理念可以概括为一句话：
“以贪心策略选择最短边，若该边不会形成环路则将其纳入边集，否则予以忽略”
为了便于具体实现，现将算法细节进一步展开：
1、将所有边按照权重大小进行排序；
2、依次遍历每条边，若该边与当前已选边不构成环路，则将其纳入集合；否则跳过；
3、当成功选取n-1条合法边时，表明图已经连通，并且最小生成树构建完成；若遍历完所有边后所选边数仍不足n-1，则说明原图不连通。
关于最小生成树的重要性质： 最小生成树同时具备最小瓶颈生成树的特征（即所选边的最大权