最小生成树(kruskal算法模版)
//kruskal算法,用优先队列解法,尽量用第一个模版 例题:挖沟:https://ac.nowcoder.com/acm/problem/17509 #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; const int N = 500010; struct node { int u,v,w; friend bool operator < (const node &x,const node &y) { return x.w > y.w; } }; int n,m,fa[N],sum; priority_queue<node> q; int find(int n) { if(fa[n] == n) return n; return fa[n] = find(fa[n]); } void un(int a,int b) { fa[find(a)] = fa[find(b)]; } void kruskal() { for(int i = 1;i <= n;i++) { fa[i] = i; } while(!q.empty()) { int u = q.top().u; int v = q.top().v; int w = q.top().w; q.pop(); if(find(u) != find(v)) { un(u,v); sum += w; } } } int main() { cin >> n >> m; sum=0; for(int i = 1;i <= m;i++) //m为边数,n为点的个数 { int a,b,v; cin >> a >> b >> v; q.push({a,b,v}); //q.push这里一定要加{ },这里比较容易出错 } kruskal(); cout << sum << endl; return 0; }
//第二个模版 #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; struct edge { ll u,v,w; }e[200010]; bool cmp(edge &a,edge &b) { return a.w<b.w; } ll f[200005],n,m,ans,cnt; ll find(ll x) { if(f[x]!=x) f[x]=find(f[x]); return f[x]; } void kruskal() { sort(e,e+m,cmp); for(int i=0;i<m;i++) { ll u=e[i].u; ll v=e[i].v; ll w=e[i].w; ll fu=find(u), fv=find(v); if(fu==fv) continue; //如果两者在一个连通图里面,continue ans+=w; f[fv]=fu; cnt++; if(cnt==n-1) break; //最小生成树只有n-1条边 } } int main() { cin >> n >> m; for(int i=1;i<=n;i++) { f[i]=i; } //每个点都自成一个连通量 for(int i=0;i<m;i++) { cin >> e[i].u >> e[i].v >> e[i].w; //输入两个端点和边的权值 } kruskal(); if(cnt!=n-1) { printf("orz"); } printf("%lld",ans); return 0; }
模版专项 文章被收录于专栏
模版