就是一个Kruskal算法模板题,但是这题目是真难读懂。

Jungle Roads

https://www.nowcoder.com/practice/75c19b92d6b942f08989b335afbc73c3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
    int from, to, val;
};
int parents[26];
int find(int x) {
    return x == parents[x] ? x : parents[x] = find(parents[x]);
}
vector<Edge> graph;
int main() {
    int n;
    while (cin >> n) {
        if (n == 0) break;
        graph.clear();
        while (--n != 0) {
            char from, to;
            int k, val;
            cin >> from >> k;
            while (k-- != 0) {
                cin >> to >> val;
                graph.push_back({from - 'A', to - 'A', val});
            }
        }
        for (int i = 0; i < 26; i++) {
            parents[i] = i;
        }
        sort(graph.begin(), graph.end(), [](Edge a, Edge b) {
            return a.val < b.val;
        });
        int ans = 0;
        for (auto edge: graph) {
            int from = find(edge.from);
            int to = find(edge.to);
            if (from != to) {
                parents[to] = from;
                ans += edge.val;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-11 11:21
被夸真的超级开心,好可爱的姐姐
码农索隆:老色批们不用脑补了,我把金智妮的图找来了查看图片
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务