HDU 1233(最小生成树,并查集)

野性酷女 2022-09-20 11:28 151阅读 0赞

这里使用kruskal:

#include <cstring>
    #include <cstdio>
    #include <queue>
    using namespace std;
    
    struct edge
    {
        int u, v, w;
        edge() {}
        edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
        bool operator <(const edge& rhs) const
        {
            return w > rhs.w;
        }
    };
    
    int set[101];
    
    int find(int x)
    {
        return set[x] < 0 ? x : set[x] = find(set[x]);
    }
    
    int main()
    {
        int n, i, u, v, w, ans;
        while (scanf("%d", &n) != EOF && n)
        {
            priority_queue<edge> q;
            memset(set, -1, sizeof set);
            ans = 0;
            for (i = 1; i <= n*(n-1)/2; ++i)
            {
                scanf("%d %d %d", &u, &v, &w);
                q.push(edge(u, v, w));
            }
            while (!q.empty())
            {
                edge p = q.top(); q.pop();
                u = find(p.u), v = find(p.v);
                if (u != v)
                {
                    set[u] += set[v];
                    set[v] = u;
                    ans += p.w;
                    if (set[u] == -n) break;
                }
            }
            printf("%d\n", ans);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关最小生成树（并查集+Kruskal算法）

小生成树问题（MST）是为了解决以最低的花费连接所有的点（使图的连通分量的数目为1）而提出的。上**并查集+Kruskal算法**求解最小生成树问题的代码： ...

╰+哭是因爲堅強的太久メ/ 2024年04月17日 18:50/ 0 赞/ 64 阅读

相关 HDU 1233(最小生成树,并查集)

这里使用kruskal: include <cstring> include <cstdio> include <queue> u

野性酷女/ 2022年09月20日 11:28/ 0 赞/ 152 阅读

相关 HDU 1232（最小生成树；并查集）

题意：如题。最小生成树建模方法：已有的边的花费为0，不存在的边花费为1，求最小生成树。 include<cstdio> include

淩亂°似流年/ 2022年09月20日 11:28/ 0 赞/ 177 阅读

相关最小生成树（kruskal） hdu 1233

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1233][http_acm.hdu.edu.cn_showproblem.ph

野性酷女/ 2022年08月27日 10:46/ 0 赞/ 175 阅读

相关并查集&&最小生成树（模板）

并查集 int find(int x){ //查查找根节点 int r=x; while(r!=pre[r]) r

小灰灰/ 2022年08月03日 15:53/ 0 赞/ 160 阅读

相关并查集 +最小生成树

并查集：并查集简单来说就是数据分类，怎么分呢，初始把数组 pre\[i\] = i 设定，表示自己归属于自己，如果A是B的老大，那么pre\[A\] = A， pre\

╰半夏微凉°/ 2022年06月10日 00:07/ 0 赞/ 208 阅读

相关 HDU-1863 畅通工程——并查集最小生成树Kruskal

畅通工程省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中

短命女/ 2022年06月07日 12:25/ 0 赞/ 186 阅读

相关连接的管道-HDU - 5253-并查集最小生成树

连接的管道老 Jack 有一片农田，以往几年都是靠天吃饭的。但是今年老天格外的不开眼，大旱。所以老 Jack 决定用管道将他的所有相邻的农田全部都串联起来，这样

红太狼/ 2022年06月06日 00:57/ 0 赞/ 186 阅读

相关 HDU1233 还是畅通工程【最小生成树】

Problem Description 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但

不念不忘少年蓝@/ 2022年01月06日 07:27/ 0 赞/ 186 阅读

相关并查集最小生成树复习

HDU 1856 more is better 简单并查集 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

一时失言乱红尘/ 2021年11月02日 14:24/ 0 赞/ 258 阅读