Krusal
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3100;
const int M=90500;
int idx=0;
int n,m;
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
bool operator> (const Edge &W)const
{
return w > W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void quick_sort(struct Edge q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1;
Edge x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int kruskal()
{
quick_sort(edges,1,1 +idx);
for (int i = 0; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 1; i <=idx; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通,则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
return res;
}
int main(){
scanf("%d",&n);
int w=0;
for(int i=1;i<=n;i++){
scanf("%d",&w);
edges[++idx].a=0,edges[idx].b=i,edges[idx].w=w;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int w;
scanf("%d",&w);
edges[++idx].a=i,edges[idx].b=j,edges[idx].w=w;
}
}
printf("%d",kruskal());
return 0;
}
//Prim
#include<iostream>
#include<cstring>
using namespace std;
const int N=310;
int n;
int w[N][N];
int dist[N];
int st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n+1; i ++ )
{
int t = -1;
for (int j = 0; j <n+1; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// if (i && dist[t] == INF) return INF;
//cout<<i<<" "<<dist[t]<<endl;
if (i) res += dist[t];
st[t] = true;
for (int j = 0; j < n+1; j ++ ) dist[j] = min(dist[j], w[t][j]);
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[0][i]);
w[i][0]=w[0][i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&w[i][j]);
w[j][i]=w[i][j];
}
}
printf("%d",prim());
return 0;
}