阅读量:0
最小生成树
概念
保证节点联通性的边权值和最小的方案
性质
若节点数为n，则最小生成树边数一定为n-1,显然。
算法1:kruskal
按权重从小到大遍历边，若会形成环，则舍去，反之保留，当保留的边数达到n-1,完成。判断是否会形成环，可用并查集判断
洛谷3366：最小生成树
模版
#include<bits/stdc++.h> using namespace std; #define N 200002 #define mod 80112002 int fa[5002]; vector<vector<int>> g(N,vector<int>(3)); int ans=0; int cnt=0; bool cmp(vector<int>&a,vector<int>&b){ return a[2]<b[2]; } int find(int x){ 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<m;i++){ cin>>g[i][0]>>g[i][1]>>g[i][2]; } sort(g.begin(),g.begin()+m,cmp); for(int i=0;i<m;i++){ if(uni(g[i][0],g[i][1])){ ans+=g[i][2]; cnt++; } if(cnt==n-1)break; } if(cnt==n-1)cout<<ans; else cout<<"orz"; return 0; } 算法2：prim算法
开始随便取一个点加入点集合，将从该点出发的边加入到优先队列（小顶堆）中。取队头的边，若该边指向的点在点集合中，则取下一条边判断，否则，将指向的点加入集合，并将从该点出发的边加入队列。如此循环直至队列为空（或集合中元素为n）
#include<bits/stdc++.h> using namespace std; #define N 200002 #define mod 80112002 typedef pair<int,int> PII; bool dis[5002]; vector<vector<PII>> g(5002); priority_queue<PII,vector<PII>,greater<PII>> q; int ans=0,cnt=1; int main(){ int n,m; cin>>n>>m; for(int i=0;i<m;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<<ans; else cout<<"orz"; return 0; } 题目
1.
https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/description/
将两个数组都排序，从小到大遍历限制数组，对于每次限制，从小到大合并符合限制的边，判断是否联通
class Solution { public: int fa[100002]; vector<bool> distanceLimitedPathsExist(int m, vector<vector<int>>& edgeList, vector<vector<int>>& queries) { int n=queries.size(); int n2=edgeList.size(); for(int i=0;i<m;i++)fa[i]=i; vector<bool> ans(n); vector<vector<int>>que(n,vector<int>(4)); for(int i=0;i<n;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<int>&a,vector<int>&b){return a[2]<b[2];}); sort(que.begin(),que.end(),[](vector<int>&a,vector<int>&b)->bool{return a[2]<b[2];}); int cnt=0; for(auto k:que){ while(cnt<n2 && edgeList[cnt][2]<k[2]){ 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
最小瓶颈树：保证联通的情况下，使得边值的最大值最小最小生成树一定是最小瓶颈树
就是求最小生成树，就不写了~~
