首页 > 其他分享 >最小生成树

最小生成树

时间：2024-09-14 10:48:43浏览次数：1  
标签：vector int MST 最小 生成 item edges heap

最小生成树

  • 最小生成树（英语：Minimum spanning tree，简称MST）是指在无向带权图中选择一些边，在保证连通性的情况下，边的总权值最小

  • 最小生成树不唯一

  • 如果无向带权图有 n 个点，最小生成树一定有 n-1 条边

P3366 【模板】最小生成树

  • Kruskal 算法
    1. 把所有的边，根据权值从小到大排序，从权值小的开始考虑
    2. 如果连接当前的边不会形成环，就把当前边加入 MST，否则跳过
    3. 考察所有的边后就能得到 MST
  • 其实就是每次找不会导致出现环的权值最小的边，依次加入到 MST
  • 时间复杂度：O(n+m) + O(m*logm)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 并查集中存放的是点的编号
vector<int> father;

void build(int n) {
    father.resize(n + 1);
    // 顶点下标从 1 开始
    for (int i = 1; i <= n; ++i)
        father[i] = i;
}

int find(int i) {
    if (i != father[i])
        father[i] = find(father[i]);
    return father[i];
}

bool isSameSet(int a, int b) {
    return find(a) == find(b);
}

void un1on(int a, int b) {
    int fa = find(a);
    int fb = find(b);
    if (fa == fb) return;
    father[fa] = fb;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges(m);
    for (int i = 0; i < m; ++i) {
        edges[i].resize(3);
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }

    // 按照边的权重排序
    sort(begin(edges), end(edges),
         [](vector<int> &a, vector<int> &b) { return a[2] < b[2]; });

    // 构建并查集
    build(n);
    // mst 的权重
    int weight = 0;
    // 已经加入 mst 的边数
    int count = 0;
    // 凑够 n - 1 条边就可以退出
    for (int i = 0; i < m && count < n - 1; ++i) {
        // 两个点在一个集合里，说明已经他俩之间已经有路径了，如果再把当前边加入 mst 就会出现环，所以跳过
        if (isSameSet(edges[i][0], edges[i][1])) continue;
        // 把两个顶点加入 mst
        un1on(edges[i][0], edges[i][1]);
        // 累加 mst 权重
        weight += edges[i][2];
        count++;
    }

    if (count == n - 1) {
        cout << weight;
    } else {
        cout << "orz";
    }
}
  • Prime 算法
    1. 解锁的点的集合叫 set，解锁的边的集合叫 heap（小顶堆），初始状态都为空。
    2. 从任意点开始，开始点加入 set，开始点的所有边加入到 heap
    3. 从 heap 中弹出权值最小的边 e，查看边 e 去往的点 x
      1. 如果 x 已经在 set 中，舍弃边 e，重复步骤 3
      2. 如果 x 不在 set 中，边 e 属于 MST，把 x 加入 set，重复步骤 3
    4. 当 heap 为空，MST 就得到了。
  • 其实就是两个集合，一个由组成 MST 的点构成的集合 A，一个为剩下元素构成的集合 B。每次从集合 B 中找到 集合 A 距离最短的点，加入到集合 A中。距离是指集合 B 中的一个点，到集合 A 中的某个点有边直接相连，且这个边的权值最小。
  • 时间复杂度：O(n+m) + O(m*logm)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 标记顶点是否已经加入 MST 的集合中
vector<bool> visited;
// 小顶堆，下标从 0 开始，pair<点的下标, 边的权值>
vector<pair<int, int>> heap;
int lenOfHeap;

// 顶点下标从 1 开始
void build(int n, int m) {
    visited.resize(n + 1, false);
    // 堆的最大容量就是边数的两倍，tmd，找了半天错才发现不是 m
    heap.resize(m * 2);
    // 堆的初始容量为 0
    lenOfHeap = 0;
}

// curIndex 为要调整位置的元素的下标
void adjustHeap(int curIndex) {
    auto temp = heap[curIndex];
    int leftChild = 2 * curIndex + 1;
    while (leftChild <= (lenOfHeap - 1)) {
        if (leftChild < (lenOfHeap - 1)
            && heap[leftChild].second > heap[leftChild + 1].second)
            leftChild++;
        if (heap[leftChild].second >= temp.second) break;
        heap[curIndex] = heap[leftChild];
        curIndex = leftChild;
        leftChild = curIndex * 2 + 1;
    }
    heap[curIndex] = temp;
}

void pushToHeap(pair<int, int> p) {
    heap[lenOfHeap] = p;
    int curIndex = lenOfHeap;
    int parentIndex = (curIndex - 1) / 2;
    lenOfHeap++;
    while (parentIndex >= 0) {
        if (heap[parentIndex].second <= p.second) break;
        heap[curIndex] = heap[parentIndex];
        curIndex = parentIndex;
        if (curIndex == 0) break;
        parentIndex = (curIndex - 1) / 2;
    }
    heap[curIndex] = p;
}

pair<int, int> getHeapTop() {
    auto res = heap[0];
    heap[0] = heap[lenOfHeap - 1];
    lenOfHeap--;
    adjustHeap(0);
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges(m);
    for (int i = 0; i < m; ++i) {
        edges[i].resize(3);
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }

    // 建堆和 visited 数组
    build(n, m);

    // 邻接表存放带权值的无向图
    vector<vector<pair<int, int>>> graph(n + 1);
    for (const auto &item: edges) {
        graph[item[0]].emplace_back(make_pair(item[1], item[2]));
        graph[item[1]].emplace_back(make_pair(item[0], item[2]));
    }

    // 任意一点作为初始点加入集合
    visited[1] = true;
    // 把初始点的相关边都入堆
    for (const auto &item: graph[1])
        // 边的另一个点的下标和边的权值入堆
        pushToHeap(make_pair(item.first, item.second));

    // MST 的权值
    int weight = 0;
    // 已经加入 MST 的边数
    int count = 0;
    // 每次选出一个与 MST 集合距离最短的顶点加入集合
    while (lenOfHeap != 0) {
        // 堆顶就是到 MST 集合距离最短的
        auto top = getHeapTop();
        // 已经在 MST 集合中，就跳过
        if (visited[top.first] == true) continue;
        // 否则把这个点加入集合
        visited[top.first] = true;
        // 累加 MST 权值
        weight += top.second;
        count++;
        // 再把与 top.first 相关的边入堆
        for (const auto &item: graph[top.first])
            pushToHeap(make_pair(item.first, item.second));
    }

    if (count == n - 1)
        cout << weight;
    else
        cout << "orz";
}

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>

using namespace std;

struct cmp {
    bool operator()(pair<int, int> &p1, pair<int, int> &p2) {
        return p1.second > p2.second;
    }
};


int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges(m);
    for (int i = 0; i < m; ++i) {
        edges[i].resize(3);
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }

    // pair<点的下标, 边的权值>
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
    // 标记顶点是否已经加入 MST 的集合中
    unordered_set<int> st;

    // 邻接表存放带权值的无向图
    vector<vector<pair<int, int>>> graph(n + 1);
    for (const auto &item: edges) {
        graph[item[0]].emplace_back(make_pair(item[1], item[2]));
        graph[item[1]].emplace_back(make_pair(item[0], item[2]));
    }

    // 任意一点作为初始点加入集合
    st.emplace(1);
    // 把初始点的相关边都入堆
    for (const auto &item: graph[1])
        // 边的另一个点的下标和边的权值入堆
        heap.push(make_pair(item.first, item.second));

    // MST 的权值
    int weight = 0;
    // 已经加入 MST 的边数
    int count = 0;
    // 每次选出一个与 MST 集合距离最短的顶点加入集合
    while (!heap.empty()) {
        // 堆顶就是到 MST 集合距离最短的
        auto top = heap.top();
        heap.pop();
        // 已经在 MST 集合中，就跳过
        if (st.find(top.first) != st.end()) continue;
        // 否则把这个点加入集合
        st.emplace(top.first);
        // 累加 MST 权值
        weight += top.second;
        count++;
        // 再把与 top.first 相关的边入堆
        for (const auto &item: graph[top.first])
            heap.push(make_pair(item.first, item.second));
    }

    if (count == n - 1)
        cout << weight;
    else
        cout << "orz";
}

  • Prime 算法优化

    1. 小顶堆里放（节点，到节点的花费也就是边的权值），根据到达节点的花费来组织小顶堆

    2. 小顶堆弹出（u 节点，到达 u 节点的花费 y），y 累加到总的权值上，然后考察 u 出发的每一条边

      假设，u 出发的边，去往 v 节点，权值 w

      A. 如果 v 已经弹出过，也就是已经加入到 MST 集合里了（MST 集合存放构成 MST 的节点），忽略该边

      B. 如果 v 还没进入过堆，就入堆，加入记录（v，w）

      C. 如果 v 在堆里，且记录为（v，x）：

      ​ a. 若 w < x，则记录改为（v，w），然后调整该记录在堆中的位置

      ​ b. 若 w >= x，忽略该边

    3. 重复步骤 2，直到小顶堆清空

  • 其中该记录的操作需要给堆加一个反向索引表，通过节点 v，找到（v，x）在堆中的位置才能将其改成（v, w）

  • 这样堆的大小就跟节点的数量相关而不是和边的数量相关

  • 优化后为时间复杂度为 O(n+m) + O((m+n)*logn)，非常适合节点少边多的情况

// todo 链式前向星 + 优化 Prime

1697. 检查边长度限制的路径是否存在

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> father;

    void build(int n) {
        father.resize(n);
        for (int i = 0; i < n; ++i)
            father[i] = i;
    }

    int find(int i) {
        if (i != father[i])
            father[i] = find(father[i]);
        return father[i];
    }

    bool isSameSet(int a, int b) {
        return find(a) == find(b);
    }

    void un1on(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return;
        father[fa] = fb;
    }

    // 顶点下标从 0 开始
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>> &edgeList, vector<vector<int>> &queries) {
        // 将边按照权值排序
        sort(begin(edgeList), end(edgeList),
             [](vector<int> &a, vector<int> &b) { return a[2] < b[2]; });

        int len = queries.size();
        vector<vector<int>> questions(len, vector<int>(4));
        for (int i = 0; i < len; ++i) {
            questions[i][0] = queries[i][0];
            questions[i][1] = queries[i][1];
            questions[i][2] = queries[i][2];
            // 多加一条记录初始问题的位置
            questions[i][3] = i;
        }
        // 也按照边长度限制进行排序
        sort(begin(questions), end(questions),
             [](vector<int> &a, vector<int> &b) { return a[2] < b[2]; });

        // 构建并查集
        build(n);
        vector<bool> res(len);
        for (int i = 0, edgeIndex = 0; i < len; ++i) {
            // 问题已按照边长度限制的大小排序，每次把小于这次边限制的所有边生成 MST，查看要求的两个点是否都在 MST 中
            // 也就是每次把点合并到 MST 集合上，然后判断要求的两个点是否属于同一个结合
            while (edgeIndex < edgeList.size() && edgeList[edgeIndex][2] < questions[i][2]) {
                un1on(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
                edgeIndex++;
            }
            res[questions[i][3]] = isSameSet(questions[i][0], questions[i][1]);
        }

        return res;
    }
};

P2330 [SCOI2005] 繁忙的都市

  • 最小瓶颈树：使图连通，且最大边尽量小
  • 最小生成树一定是最小瓶颈树
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> father;

void build(int n) {
    father.resize(n + 1);
    for (int i = 1; i <= n; ++i)
        father[i] = i;
}

int find(int i) {
    if (i != father[i])
        father[i] = find(father[i]);
    return father[i];
}

bool isSameSet(int a, int b) {
    return find(a) == find(b);
}

void un1on(int a, int b) {
    int fa = find(a);
    int fb = find(b);
    if (fa == fb) return;
    father[fa] = fb;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> edges(m, vector<int>(3));
    for (int i = 0; i < m; ++i)
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];

    // 按照边的权值排序
    sort(begin(edges), end(edges),
         [](vector<int> &a, vector<int> &b) { return a[2] < b[2]; });

    build(n);

    int count = 0;
    int res;
    for (int i = 0; i < m && (count < n - 1); ++i) {
        if (isSameSet(edges[i][0], edges[i][1])) continue;
        un1on(edges[i][0], edges[i][1]);
        count++;
        if (count == n - 1) res = edges[i][2];
    }

    cout << n - 1 << " " << res;
}

标签：vector,int,MST,最小,生成,item,edges,heap
From： https://www.cnblogs.com/sprinining/p/18413494

相关文章

  • MemLong: 基于记忆增强检索的长文本LLM生成方法
    本文将介绍MemLong，这是一种创新的长文本语言模型生成方法。MemLong通过整合外部检索器来增强模型处理长上下文的能力，从而显著提升了大型语言模型（LLM）在长文本处理任务中的表现。核心概念MemLong的设计理念主要包括以下几点：高效扩展LLM上下文窗口的轻量级方法。利用不可训练的......
  • PbootCMS生成的sitemap.xml中增加tag标签链接
    打开/apps/home/model/SitemapModel.php，在78行后面增加个指定分类标签调用代码//指定分类标签调用publicfunctiongetSortTags($scode){$join=array(array('ay_content_sortb','a.scode=b.scode','LEFT'......
  • 降低AI味儿，垂直领域的超级助手！百度文小言一键生成网文小说的完整方法
    不绕圈子了，直接切入正题！今天我们要聊的，是如何用AI智能体轻松写出一部网文小说。而重点是——降低AI味儿！没错，这个智能体已经训练到，能生成情节完整、角色饱满、逻辑清晰、文笔自然的小说，让你几乎看不出这是AI的作品。网文智能体是什么鬼？先来搞清楚什么是网文智能体。......
  • 【随想录day2】LeetCode209长度最小的子数组 | LeetCode59螺旋矩阵
    LeetCode209长度最小的子数组1、题目：给定一个含有n个正整数的数组和一个正整数s，找出该数组中满足其和≥s的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回0示例：输入：s=7,nums=[2,3,1,2,4,3]输出：2解释：子数组[4,3]是该条件下的长度最小......
  • Day2|209.长度最小的子数组|59.螺旋矩阵II|区间和|开发商购买土地
    209.长度最小的子数组59.螺旋矩阵II 209.长度最小的子数组classSolution{publicintminSubArrayLen(inttarget,int[]nums){intfastIndex=0;intslowIndex=0;intsums=0;intresult=Integer.MA......
  • 生成AI带货虚拟主播会用到的源代码!
    在当今数字化时代，AI带货虚拟主播已成为电商行业的新宠，它们不仅能够24小时不间断地进行产品展示和销售，还能通过智能交互提升用户体验。今天，我们将深入探讨AI带货虚拟主播背后的技术实现，并分享六段关键的源代码，帮助大家更好地理解这一前沿领域。一、AI带货虚拟主播简介AI带货虚拟主播......
  • AI生成头像表情包，一次十分钟，就能实现月入过万的玩法，无脑操作
    今天给大家带来的项目是AI生成表情包和头像，这个项目对于我们做ip来说是真心不错，就比如我这个头像。为什么说每天只需要10分钟呢，那么我们继续往下看。"项目介绍这个项目的核心其实就是使用AI生成表情包或者说生成头像，我们再小红书上运营一个账号，通过发布图文吸引粉丝。......
  • 随机生成加减法题目函数
    importrandomfromdocximportDocument#创建一个新文档doc=Document()doc.add_heading('100以内连续加减法训练题',level=1)#随机生成加减法题目函数defgenerate_question():num1=random.randint(1,100)num2=random.randint(1,100)num3=r......
  • ERP的MPS如何设计，它关系到哪些画面，各自之间的关系是什么，如何根据订单生成工单、物料需
    在ERP系统中，主生产计划（MPS,MasterProductionSchedule）的设计是核心环节之一，主要用于确定生产和物料的需求。MPS通常依赖于客户订单、预测需求以及库存情况来生成一个综合的生产计划。其设计涉及多个模块或画面，以下是MPS设计的关键流程和模块：1.MPS设计的模块和画面MPS系统通......
  • 生成器yield，next()与send()
    #把a创建成了一个生成器对象generatorobjecta=(x*2forxinrange(10))print(a)print(next(a))#生成器对象调用用next(a)，等价于a.__next__(),生成器一次调用一个print(next(a))foriina:#生成器是一个可迭代对象print(i)#创建生成器的第二种方式......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99