最小生成树
最小生成树
Prim算法
朴素Prim
O(n^2)
步骤:
- 初始化:把每个点到集合的距离设为正无穷
- 每次找到集合外距离最近的点u
- 用u来更新其它点到 集合 的距离(Dijkstra中,更新的是到起点的距离)
acwing 858
(其实就是把下面那道洛谷模板题的数据换成稠密图)
(1≤n≤500, 1≤m≤10^5)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=510; const int inf=0x3f3f3f3f; int n,m; int in[N],dis[N],g[N][N]; int ans=0,flag=0; void prim() { memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=n;i++) { int t=-1; for(int j=1;j<=n;j++) { if(!in[j] and (t==-1 or dis[t]>dis[j])) { t=j; } } if(i>1 and dis[t]==inf)flag=1; if(flag)break; if(i>1)ans+=dis[t]; for(int j=1;j<=n;j++) { dis[j]=min(dis[j],g[t][j]); } in[t]=1; } } int main() { ios::sync_with_stdio(0); cin>>n>>m; memset(g,0x3f,sizeof(g)); for(int i=1;i<=m;i++) { int u,v,w; cin>>u>>v>>w; g[u][v]=g[v][u]=min(g[u][v],w); } prim(); if(flag)cout<<"impossible"; else cout<<ans; return 0; }
|
堆优化Prim算法(不常用,类似Dijkstra)
O(m logn)
Kruskal 算法
O(m logm)
步骤:
- 将所有边按权值从小到大排序,时间复杂度O(m logm)
- 枚举每条边 u-v (权w)。如果u,v不连通,就将这条边加入集合中。(并查集)
洛谷P3366 【模板】最小生成树
题目描述
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz
。
输入格式
第一行包含两个整数 N,MN,M,表示该图共有 NN 个结点和 MM 条无向边。
接下来 MM 行每行包含三个整数 X_i,Y_i,Z_i,表示有一条长度为 Z_i 的无向边连接结点 X_i,Y_i。
输出格式
如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz
。
输入输出样例
输入 #1
1 2 3 4 5 6
| 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
|
输出 #1
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=200050; struct node { int u,v,w; }e[N]; int n,m; int fa[N]; int cnt=0,res=0,tot=0; void add(int u,int v,int w) { e[++cnt].v=v; e[cnt].u=u; e[cnt].w=w; } bool cmp(node a,node b) { return a.w<b.w; } int find(int x) { if(x==fa[x])return x; return fa[x]=find(fa[x]); } int main() { ios::sync_with_stdio(0); cin>>n>>m; for(int i=1;i<=m;i++) { int u,v,w; cin>>u>>v>>w; add(u,v,w); } sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++) { fa[i]=i; } for(int i=1;i<=m;i++) { int u=e[i].u,v=e[i].v,w=e[i].w; u=find(u),v=find(v); if(u!=v) { res+=w; tot++; fa[u]=v; } } if(tot<n-1)cout<<"orz"; else cout<<res; return 0; }
|