最小生成树
创始人
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
最小瓶颈树：保证联通的情况下，使得边值的最大值最小最小生成树一定是最小瓶颈树
就是求最小生成树，就不写了~~
相关内容
热门资讯
专业讨论!德扑线上有机器人,太...
专业讨论!德扑线上有机器人,太坑了从来存在有挂(2020已更新)(哔哩哔哩)；详细德扑线上有机器人攻...
带你了解!微扑克线上代打工具,...
带你了解!微扑克线上代打工具,太坑了本然是有挂(2024已更新)(哔哩哔哩)；微扑克线上代打工具简单...
六分钟了解!德州ai辅助神器靠...
六分钟了解!德州ai辅助神器靠谱,太坑了起初真的是有挂(2022已更新)(哔哩哔哩);1、超多福利：...
玩家必看科普!德扑数据软件,太...
玩家必看科普!德扑数据软件,太坑了最初是真的有挂(2024已更新)(哔哩哔哩)；致您一封信；亲爱德扑...
最新技巧!微扑克网页版辅助,太...
最新技巧!微扑克网页版辅助,太坑了好像真的有挂(2023已更新)(哔哩哔哩)；微扑克网页版辅助简单的...
必知教程!德扑之星窥牌,太坑了...
必知教程!德扑之星窥牌,太坑了确实真的是有挂(2026已更新)(哔哩哔哩);1、让任何用户在无需AI...
第三方辅助挂!wopoker用...
第三方辅助挂!wopoker用ai有用,太坑了从前真的有挂(2025已更新)(哔哩哔哩);一、wop...
玩家必知教程!微扑克后台能控制...
玩家必知教程!微扑克后台能控制胜率,太坑了总是真的有挂(2023已更新)(哔哩哔哩);AI辅助机器人...
实测必看!微扑克ai辅助神器,...
实测必看!微扑克ai辅助神器,太坑了原来真的有挂(2024已更新)(哔哩哔哩)；1.微扑克ai辅助神...
黑科技免费!德州辅助,太坑了从...
黑科技免费!德州辅助,太坑了从来是真的有挂(2026已更新)(哔哩哔哩)相信很多朋友都在电脑上玩过德...