[leetcode] 连接所有点的最小费用 -MST

简介: 这道题是最小生成树板子题可以用并查集实现,贪心排序边权讲一个二元组放在一个vector容器里面,其中的元素为<weight,<u,v>>对应<int,<int,int> >类型,第一个参数代表边权的大小,后面的为两个点u,v,然后按照第一个值边权从小到大排序,然后用并查集实现是否连通,从而实现最小生成树代码有点套娃(

题目链接


21109b92aaa14dbda2cf559bb96c39eb.png

这道题是最小生成树板子题


可以用并查集实现,贪心排序边权

讲一个二元组放在一个vector容器里面,其中的元素为<weight,<u,v>>对应<int,<int,int> >类型,第一个参数代表边权的大小,后面的为两个点u,v,然后按照第一个值边权从小到大排序,然后用并查集实现是否连通,从而实现最小生成树

代码有点套娃(


class Solution {
private:
    int fa[1007];
    int cnt = 0;
    typedef pair<int, pair<int, int> > pir;
    void init() {
        for (int i = 0; i < 1007; i++) fa[i] = i;
    }
    int _find(int u) {
        if (fa[u] == u) return u;
        else return fa[u] = _find(fa[u]);
    }
public:
    int minCostConnectPoints(vector<vector<int>> &points) {
        init();
        vector<pir> vt;
        int n = points.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int wei = abs(points[i][0] - points[j][0]);
                wei += abs(points[i][1] - points[j][1]);
                vt.push_back({wei, {i, j}});
            }
        }
        sort(vt.begin(), vt.end(), [](pir p1, pir p2) {
            return p1.first < p2.first;
        });
        long long out = 0;
        int lim = vt.size();
        for (int i = 0; i < lim; i++) {
            int u = vt[i].second.first;
            int v = vt[i].second.second;
            int fau = _find(fa[u]);
            int fav = _find(fa[v]);
            if (fau == fav) continue;
            else {
                fa[fau] = fav;
                out += vt[i].first;
            }
        }
        return out;
    }
};


文章知识点与官方知识档案匹配,可进一步学习相关知识

算法技能树leetcode-动态规划22-括号生成8242 人正在系统学习中


目录
相关文章
|
算法 C++ Python
每日算法系列【LeetCode 685】冗余连接 II
每日算法系列【LeetCode 685】冗余连接 II
|
算法 C++ Python
每日算法系列【LeetCode 684】冗余连接
每日算法系列【LeetCode 684】冗余连接
leetcode 685 冗余连接II
leetcode 685 冗余连接II
90 0
leetcode 685 冗余连接II
|
算法
【Day30】LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]
学习LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]。
117 0
【Day30】LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]
Leetcode | 连接两字母单词得到的最长回文串
Leetcode | 连接两字母单词得到的最长回文串
144 0
Leetcode | 连接两字母单词得到的最长回文串
【day09】LeetCode(力扣)每日一刷[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]
学习了解[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]。
97 0
【day09】LeetCode(力扣)每日一刷[1640. 能否连接形成数组 ][102. 二叉树的层序遍历 ][704. 二分查找 ]
LeetCode每日一题——1640. 能否连接形成数组
如果可以连接 pieces 中的数组形成 arr ,返回 true ;否则,返回 false 。
76 0
|
机器学习/深度学习 自然语言处理 算法
每日算法系列【LeetCode 685】冗余连接 II
在本问题中,有根树指满足以下条件的有向图。该树只有一个根节点,所有其他节点都是该根节点的后继。每一个节点只有一个父节点,除了根节点没有父节点。
131 0
每日算法系列【LeetCode 685】冗余连接 II