牛子爷得到了一副地图？(关键词-字典序)

Question

牛子爷得到了一副地图，他想保留图的一些边后让图上的任意两点都能通过这些边互相到达。他想知道保留这些边的最小花费是多少？边为无向边。
多组输入。每个数据第一行为图中点的个数。紧接着n-1行，每行的第一个字母为图中的某一个点，（按照字典序升序），第二个数字表示这个点与比它字典序大的相连点的个数，然后后面紧接着为相连边的花费。 当地图中点的个数为0时，输入结束。
保证可以联通。

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7632875
• 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：3.19√ 假设一个算术表达式中可以包含三种括号：圆括号、方括号、花括号。编写判别给定表达式中所含括号是否正确配对出现的算法
• 除此之外, 这篇博客: C语言实现八大排序算法详解及其性能之间的中的 这里需要对堆有一定的了解，堆就是一个比较特殊的完全二叉树，在最大堆里，每个节点的值都大于其左右两个孩子节点的值。这就是最大堆。反之就是最小堆。拿最大堆举例子，每次堆顶的元素值，不就是当前数列的最大吗？这不就成选择排序里的简单排序了吗？找完之后，将他和完全二叉树里最后一个结点的值进行交换，然后做一个自顶向下的自我调整，将他再次调整成一个完全二叉堆。第二次取最大的树，这时我们需要将上一次找到的结点屏蔽掉，不然会陷入一个死循环。无数次找完之后，再按层序的思想将二叉树里的数据遍历到一个数组当中，这时的数组为一个有序的数组。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  算法思想

• 您还可以看一下 李月喜老师的企业微信开发第三方应用开发篇课程中的 第三方市场分析，安装试用第三方网页应用及小程序应用，了解安装及授权安装流程小节, 巩固相关知识点
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

Answer 2

这个问题可以使用最小生成树算法来解决。最小生成树算法用于在一个加权无向图中找到一棵包含所有点的生成树，使得所有边的权重之和最小。

具体地，可以使用Kruskal算法或Prim算法来实现最小生成树。以下是一个使用Kruskal算法实现的伪代码：

定义一个边的结构体，包含起点、终点和边权重。

定义一个优先队列（最小堆），用于存储所有边，按照边权重从小到大排序。

初始化一个并查集，用于判断两个节点是否在同一连通分量中。

将所有边加入优先队列中。

从优先队列中依次取出边，如果该边的两个端点不在同一连通分量中，则将这条边加入最小生成树中，并把这两个端点合并到同一连通分量中。

当最小生成树中边的数量达到n-1时（n为节点数），停止算法。

最小生成树的权重即为所求。

伪代码：

```c
struct Edge {
    int from, to, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

int n; // 节点数
vector<Edge> edges; // 所有边
vector<int> parent; // 并查集数组

int find(int x) { // 并查集查找
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}

int kruskal() {
    sort(edges.begin(), edges.end()); // 将所有边按照权重从小到大排序
    parent.resize(n);
    for (int i = 0; i < n; i++) parent[i] = i; // 初始化并查集
    int ans = 0, cnt = 0;
    for (auto& e : edges) {
        int x = find(e.from), y = find(e.to);
        if (x != y) {
            parent[x] = y; // 合并两个连通分量
            ans += e.weight; // 加入最小生成树
            cnt++;
            if (cnt == n - 1) break; // 达到n-1条边，停止算法
        }
    }
    return ans;
}

int main() {
    while (cin >> n && n) {
        // 读入所有边
        edges.clear();
        for (int i = 0; i < n - 1; i++) {
            char u; int k;
            cin >> u >> k;
            for (int j = 0; j < k; j++) {
                char v; int w;
                cin >> v >> w;
                edges.push_back({u - 'A', v - 'A', w});
            }
        }
        int ans = kruskal(); // 求解最小生成树
        cout << ans << endl;
    }
    return 0;
}

```