最小生成树
创始人
2024-11-12 04:39:14
0次

最小生成树

  • 概念
  • 性质
  • 算法1:kruskal
  • 算法2：prim算法
  • 题目
    • 1.
    • 2.繁忙的都市 洛谷-2330

概念

保证节点联通性的边权值和最小的方案

性质

若节点数为n，则最小生成树边数一定为n-1,显然。

算法1:kruskal

按权重从小到大遍历边，若会形成环，则舍去，反之保留，当保留的边数达到n-1,完成。判断是否会形成环，可用并查集判断

洛谷3366：最小生成树
模版

#include using namespace std; #define N 200002 #define mod 80112002 int fa[5002]; vector> g(N,vector(3)); int ans=0; int cnt=0; bool cmp(vector&a,vector&b){     return a[2]     if(x!=fa[x])fa[x]=find(fa[x]);     return fa[x]; } bool uni(int x,int y){     int fx=find(x),fy=find(y);     if(fx!=fy){         fa[fy]=fx;         return true;     }     return false; } int main(){     int n,m;     cin>>n>>m;     for(int i=1;i<=n;i++)fa[i]=i;     for(int i=0;i         cin>>g[i][0]>>g[i][1]>>g[i][2];     }     sort(g.begin(),g.begin()+m,cmp);     for(int i=0;i         if(uni(g[i][0],g[i][1])){             ans+=g[i][2];             cnt++;         }         if(cnt==n-1)break;     }     if(cnt==n-1)cout<

算法2：prim算法

开始随便取一个点加入点集合，将从该点出发的边加入到优先队列（小顶堆）中。取队头的边，若该边指向的点在点集合中，则取下一条边判断，否则，将指向的点加入集合，并将从该点出发的边加入队列。如此循环直至队列为空（或集合中元素为n）

#include using namespace std; #define N 200002 #define mod 80112002 typedef pair PII; bool dis[5002]; vector> g(5002); priority_queue,greater> q; int ans=0,cnt=1; int main(){     int n,m;     cin>>n>>m;     for(int i=0;i         int x,y,z;         cin>>x>>y>>z;         g[x].push_back({z,y});         g[y].push_back({z,x});     }     for(auto x: g[1]){         q.push(x);     }     dis[1]=true;     while(!q.empty()){         PII now=q.top();         q.pop();         if(dis[now.second])continue;         ans+=now.first;         cnt++;         if(cnt==n)break;         dis[now.second]=true;         for(auto x: g[now.second]){             q.push(x);         }     }     if(cnt==n)cout<

题目

1.

https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/description/

将两个数组都排序，从小到大遍历限制数组，对于每次限制，从小到大合并符合限制的边，判断是否联通

class Solution { public:     int fa[100002];     vector distanceLimitedPathsExist(int m, vector>& edgeList, vector>& queries) {         int n=queries.size();         int n2=edgeList.size();         for(int i=0;i ans(n);         vector>que(n,vector(4));         for(int i=0;i             que[i][0]=queries[i][0];             que[i][1]=queries[i][1];             que[i][2]=queries[i][2];             que[i][3]=i;         }         sort(edgeList.begin(),edgeList.end(),[](vector&a,vector&b){return a[2]&a,vector&b)->bool{return a[2]             while(cnt                 uni(edgeList[cnt][0],edgeList[cnt][1]);                 cnt++;             }             ans[k[3]]=(find(k[0])==find(k[1]));         }         return ans;     }     void uni(int x,int y){         int fx=find(x),fy=find(y);         if(fx!=fy)fa[fy]=fx;     }     int find(int x){         if(x!=fa[x])fa[x]=find(fa[x]);         return fa[x];     } };

2.繁忙的都市 洛谷-2330

最小瓶颈树：保证联通的情况下，使得边值的最大值最小
最小生成树一定是最小瓶颈树
就是求最小生成树，就不写了~~

上一篇：嵌入式C++、STM32、Flask框架、SQL、ROS系统和MQTT协议通讯：智能药盒及物联网数据监测设计思路（代码示例）

下一篇：【C++】—— 类与对象（二）

相关内容

热门资讯

微扑克总结！德扑之星能开挂透视... 微扑克总结！德扑之星能开挂透视吗（辅助），总是真的有辅助工具是一款可以让一直输的玩家，快速成为一个“...
WePoKer必备！德扑之星是... 您好，德扑之星是不是有人用挂这款游戏可以开挂的，确实是有挂的，需要了解加微【136704302】很多...
aapoker必备！wepok... 一款 AI 游戏攻略黑科技工具上线，查攻略效率直接开挂。它整合版本更新、装备搭配、BOSS 打法、牌...
菠萝智星德州普及！WePoKe... 菠萝智星德州普及！WePoKer辅助挂怎么下载（透视挂），好像有透视挂脚本是一款可以让一直输的玩家，...
WePoKer揭露！wepok... 您好，wepoker辅助工具好用吗这款游戏可以开挂的，确实是有挂的，需要了解加微【485275054...
德扑之星总结！wepoker有... 很多人使用云端 AI 时，都担心wepoker有挂吗作弊、内部资料上传带来隐私风险。这款本地运行的 ...
红龙PoKer解谜！安卓wep... 您好：安卓wepoker德州透视挂下载这款游戏可以开挂的，确实是有挂的，很多玩家在这款游戏中打牌都会...
wpk分享！wepokerpu... wpk分享！wepokerpus透视挂是真的假的（辅助器），素来真的有辅助器神器是一款可以让一直输的...
aapoker总结！wepok... AI 黑科技赛道又上新，这款智能处理工具堪称效率开挂，专门面向短视频创作者打造。它打通脚本撰写、AI...
微扑克曝光！runit德州透视... 微扑克曝光！runit德州透视软件辅助挂（开挂），一向有开挂插件是一款可以让一直输的玩家，快速成为一...