传送门
最小生成树模板题
#include <iostream>
#include <cstring>
using namespace std;
const int N = 55, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool vis[N];
int p, r;
int prim(){
memset(dist, INF, sizeof dist);
int res = 0, cnt = 0;
for(int i = 0; i < p; i ++){
int t = -1;
for(int j = 1; j <= p; j ++)
if(!vis[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if(i) res += dist[t];
for(int j = 1; j <= p; j ++)
dist[j] = min(dist[j], g[t][j]);
vis[t] = true;
}
return res;
}
int main(){
while(cin >> p){
if(p == 0)
break;
cin >> r;
memset(vis, 0, sizeof vis);
memset(g, INF, sizeof g);
while(r --){
int u, v, w;
cin >> u >> v >> w;
g[u][v] = g[v][u] = min(g[u][v], w);
}
cout << prim() << endl;
}
return 0;
}
//kruskal算法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
struct Edge{
int u, v, w, next;
}edge[N];
int n, m, fa[N];
bool cmp(Edge a, Edge b){
return a.w < b.w;
}
int find(int x){
if(x != fa[x])
fa[x] = find(fa[x]);
return fa[x];
}
int main(){
while(cin >> n){
if(n == 0)
break;
cin >> m;
for(int i = 0; i < m; i ++){
int u, v, w;
cin >> u >> v >> w;
edge[i].u = u;
edge[i].v = v;
edge[i].w = w;
}
sort(edge, edge + m, cmp);
for(int i = 1; i <= n; i ++)
fa[i] = i;
int res = 0, cnt = 0;
for(int i = 0; i < m; i ++){
int a = edge[i].u, b = edge[i].v, w = edge[i].w;
a = find(a), b = find(b);
if(a != b){
fa[a] = b;
cnt ++;
res += w;
}
}
cout << res << endl;
}
return 0;
}