3 条题解
-
0
// Kruskal算法 O(mlogm) #include<bits/stdc++.h> using namespace std; const int N=200010; int n,m; int fa[N],ans,tot; pair<int,pair<int,int> >e[N]; //边集 int find(int u){ //并查集的找根 return fa[u]==u?u:fa[u]=find(fa[u]); } void kruskal(){ for(int i=1;i<=n;i++) fa[i]=i; sort(e+1,e+1+m); //排序 for(int i=1;i<=m;i++){ int x=find(e[i].second.first),y=find(e[i].second.second); if(x!=y){ fa[x]=y; ans+=e[i].first; if(++tot==n-1) break; } } if(tot==n-1) printf("%d\n",ans); else puts("orz"); } int main(){ cin>>n>>m; for(int i=1,u,v,w;i<=m;i++){ cin>>u>>v>>w; e[i]={w,{u,v}}; } kruskal(); } -
0
// Prim算法 O(n^2) #include<bits/stdc++.h> using namespace std; const int N=5010; int n,m,cnt,ans; vector<pair<int,int>> e[N]; int d[N],vis[N]; //d[i]表示点i到集合内点的最小边权 void prim(){ for(int i=0;i<=n;i++) d[i]=1e9; d[1]=0; for(int i=1,u;i<=n;i++){ u=0; //0点很大 for(int j=1;j<=n;j++)if(!vis[j]&&d[j]<d[u]) u=j; vis[u]=1; //选出最优点 if(u) cnt++; //点数 ans+=d[u]; //边权和 for(auto [v,w]:e[u])if(d[v]>w) d[v]=w; } if(cnt==n) printf("%d\n",ans); else puts("orz"); } int main(){ cin>>n>>m; for(int i=0,a,b,c; i<m; i++){ cin>>a>>b>>c; e[a].push_back({b,c}); e[b].push_back({a,c}); } prim(); }// 堆优化的 Prim 算法 O(mlogm) #include<bits/stdc++.h> using namespace std; #define inf 1e9 const int N=5010; int n,m,ans,cnt; vector<pair<int,int>> e[N]; int d[N],vis[N]; //d[v]表示v到已选集合的最短距离 bool prim(int s){ for(int i=0;i<=n;i++) d[i]=inf; d[s]=0; priority_queue<pair<int,int>> q; //大根 q.push({0,s}); //起点入队 while(q.size()){ int u=q.top().second; q.pop(); if(vis[u]) continue; //第1次出队才扩展 vis[u]=1; ans+=d[u]; //边权和 cnt++; //节点个数 for(auto t:e[u]){ int v=t.first, w=t.second; if(d[v]>w){ //松弛 d[v]=w; q.push({-d[v],v}); //入队 } } } return cnt==n; } int main(){ cin>>n>>m; for(int i=1,a,b,c; i<=m; i++){ cin>>a>>b>>c; e[a].push_back({b,c}); e[b].push_back({a,c}); } if(!prim(1)) puts("orz"); else printf("%d\n",ans); } -
0
【算法速成课1 | 题解】洛谷P3366 【模板】最小生成树 MST（Prim & Kruskal）-CSDN博客
/* Kruskal： Kruskal 算法也是一种贪心算法，但它是基于边的选择： 将所有边按权重从小到大排序。 依次选择最小权重的边。 如果该边连接的两个顶点不在同一连通分量中（不形成环），则加入生成树。 重复步骤 2 和 3，直到选够 N - 1 条边（N 是节点个数）。 */ #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10; typedef long long LL; int fa[N]; struct node { int x, y; LL v; } a[N]; bool cmp(node na, node nb) { return na.v < nb.v; } int findfa(int x) { if (fa[x] == x) { return fa[x]; } return fa[x] = findfa(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> a[i].x >> a[i].y >> a[i].v; } for (int i = 1; i <= n; i++) { fa[i] = i; } LL ans = 0; //累计答案 int sum = 0; //累计已选的边数 sort(a + 1, a + m + 1, cmp); for (int i = 1; i <= m; i++) { int tx = findfa(a[i].x); int ty = findfa(a[i].y); if (tx != ty) { sum ++; ans += a[i].v; fa[tx] = ty; } if (sum == n - 1) { //找够边就退出 break; } } if (sum < n - 1) { //都结束了还选不到 n - 1 条合适的边，包不连通的 cout << "orz" << "\n"; return 0; } cout << ans << "\n"; return 0; } /*Prim 算法是一种贪心算法，从一个起始顶点开始，逐步扩展生成树： 从任意顶点开始，将其加入生成树集合。 重复选择与当前生成树相连的最小权重边。 将新顶点加入生成树，直到覆盖所有顶点。 */ #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 5e5 + 10; struct node{ int x; LL v; } ; vector<node> G[N]; bool v[N]; //v[i]：为 ture就是 i走过，反之则没有 int n, m; bool operator<(node na, node nb) { return na.v > nb.v; } void Prim(){ LL ans = 0; priority_queue<node> Q; memset(v, 0, sizeof(v)); int st = 1, sum = 1; // st：起始点，sum：走过多少点 v[st] = 1; for(auto i: G[st]) { Q.push(i); } int Time = 0; //特判是否是连通图用的循环次数计数 while (sum < n) { if (Time > 3 * m) { //每条边最多走两遍，超过三遍那肯定不连通 cout << "orz" << "\n"; return ; } Time++; //不能放下面那个 if(v)下面！！！ auto Head = Q.top(); Q.pop(); int x = Head.x; if (v[x]) { //虽然下面进堆之前就特判了 //但是历史遗留的边的点可能已经走过了 continue; } v[x] = 1; sum++; ans += Head.v; for (auto j: G[x]) if(!v[j.x]) { Q.push(j); } } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { int x, y; LL v; cin >> x >> y >> v; G[x].push_back({y, v}); G[y].push_back({x, v}); } Prim(); return 0; }
- 1