最小生成树
创始人
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
最小瓶颈树：保证联通的情况下，使得边值的最大值最小最小生成树一定是最小瓶颈树
就是求最小生成树，就不写了~~
相关内容
热门资讯
透视了解！sohoo开挂辅助，...
透视了解！sohoo开挂辅助，海南骨牌辅助器免费，窍门教程（有挂秘诀）-哔哩哔哩1、海南骨牌辅助器免...
曝光透视！wepoker一直输...
曝光透视！wepoker一直输的号能继续打吗，广西微乐小程序辅助器，讲义教程（有挂头条）-哔哩哔哩1...
刚刚！闲娱江西修改器，雀神挂件...
刚刚！闲娱江西修改器，雀神挂件价格辅助开挂，攻略教程（有挂详情）-哔哩哔哩刚刚！闲娱江西修改器，雀神...
迎来新发展！pokemmo辅助...
迎来新发展！pokemmo辅助脚本，拱趴大菠萝辅助工具下载，步骤教程（有挂猫腻）-哔哩哔哩拱趴大菠萝...
总结透视！wpk辅助插件，微乐...
总结透视！wpk辅助插件，微乐自建房辅助软件功能，教材教程（有挂规律）-哔哩哔哩wpk辅助插件透视方...
截至目前！枫叶辅助器，微信边锋...
截至目前！枫叶辅助器，微信边锋辅助挂件，方针教程（发现有挂）-哔哩哔哩微信边锋辅助挂件能透视中分为三...
透视安装！pokemmo手机脚...
透视安装！pokemmo手机脚本，冰球突破豪华版辅助，机巧教程（证实有挂）-哔哩哔哩1、每一步都需要...
解密透视！德普辅助器怎么用，微...
解密透视！德普辅助器怎么用，微乐麻将脚本透视，步骤教程（有挂存在）-哔哩哔哩1、德普辅助器怎么用透视...
据目击者称！佛手大菠萝辅助，唯...
据目击者称！佛手大菠萝辅助，唯思竞技游戏辅助，积累教程（有挂秘籍）-哔哩哔哩一、唯思竞技游戏辅助可以...
来临！德州局透视脚本，财神十三...
来临！德州局透视脚本，财神十三章如何提高运气，教材教程（有挂规律）-哔哩哔哩1、该软件可以轻松地帮助...