参考:https://www.cnblogs.com/guanlexiangfan/p/15178069.html
参考:https://blog.csdn.net/win_star_/article/details/106139956
算法的核心思想是贪心,类似于 kruskal
算法过程:
1. 维护途中所有联通块,然后遍历所有点和边。
2. 找到每一个联通块和其他联通块相连的最小的一条边。
3. 把连通块合并起来,重复操作,直到剩下一整个连通块。
复杂度分析:
复杂度是 \(O((m+n)\log{n})\) ,每次合并两个连通块,进行 \(log\) 次就能完成。
【代码】
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int nxt[N],ver[N],tot,edge[N],head[N]; int n,m,fa[N],mn[2][N],ans; /* mn第一维存fx这个节点距离其他节点最小的长度 第二维存当前连通块的缩点的点 */ void add(int x,int y,int z){ ver[++tot]=y; edge[tot]=z; nxt[tot]=head[x]; head[x]=tot; } int get(int x){ if(x==fa[x]) return x; else return fa[x]=get(fa[x]); } void merge(int x,int y){ int fx=get(x),fy=get(fy); fa[fx]=fy; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } while(1){ memset(mn[0],127,sizeof(mn[0])); bool flag=0; for(int x=1;x<=n;x++) for(int i=head[x];i;i=nxt[i]){ int y=ver[i],fx=get(x),fy=get(y); if(fx==fy) continue; if(mn[0][fx]>edge[i]){ mn[0][fx]=edge[i]; mn[1][fx]=fy; } } for(int i=1;i<=n;i++) if(mn[0][i]!=mn[0][0]&&get(i)!=get(mn[1][i])) flag=1,ans+=mn[0][i],merge(i,mn[1][i]); if(!flag) break; } for(int i=1;i<n;i++) if(get(i)!=get(i+1)){ puts("NO"); return 0; } cout<<ans<<endl; return 0; }