最小生成树 kruskal
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn = 2e5+7; const int INF = 0x3f3f3f; typedef pair<int,int>PII; vector<PII>g[maxn] ; int vis[maxn] ,fa[maxn]; struct node{ int w,v,u; }p[maxn]; bool cmp(node x,node y) { return x.w<y.w ; } int n, m; int findfa(int x) { if(x==fa[x])return x ; else return findfa(fa[x]); } int main() { ll ans = 0 ,cnt =0 ; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)fa[i] = i; for(int i=1;i<=m;i++) { scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w); } sort(p+1,p+1+m,cmp); for(int i=1;i<=m;i++) { int fu = findfa(p[i].u); int fv = findfa(p[i].v); if(fu == fv)continue; ans += p[i].w ; fa[fv] = fu; if(++cnt == n-1)break; } if(cnt == n-1)printf("%lld",ans) ; else printf("orz"); return 0 ; }最小生成树 Prim
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn = 2e5+7; const int INF = 0x3f3f3f; typedef pair<int,int>PII; vector<PII>g[maxn] ; int vis[maxn],dis[maxn]; int n,m,u,v,w ; int main() { int cnt=0; ll ans = 0 ; scanf("%d%d",&n,&m) ; for(int i=1;i<=n;i++)dis[i]= INF; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); g[u].push_back({v,w}); g[v].push_back({u,w}); } priority_queue<PII,vector<PII>,greater<PII> > que ; dis[1] =0 ; que.push({0,1}); while(!que.empty()&& cnt<n ) { int val = que.top().first, nxt = que.top().second; que.pop(); if(vis[nxt])continue; cnt++ ; ans+= val ; vis[nxt] =1; for(int i = 0;i<g[nxt].size();i++) { int v = g[nxt][i].first; int w = g[nxt][i].second; if(dis[v]>w ) { dis[v] =w; que.push({dis[v],v}); } } } if(n==cnt )printf("%lld",ans); else printf("orz"); return 0; }