最近算法课讲到了最小生成树,就来复习一下prim和Kruskal的写法吧
Prim MST
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 200010;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int Prim()
{
int res=0;
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for (int i=0;i<n;i++)
{
int t = -1;
for (int j=1;j<=n;j++)
{
if (!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
st[t] = true;
res+=dist[t];
if (dist[t]==0x3f3f3f3f) return 0x3f3f3f3f; // 此时集合中最小的点还是正无穷,说明一定无解
for (int j=1;j<=n;j++)
dist[j] = min(dist[j],g[t][j]);
}
return res;
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
while (m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
int ans = Prim();
if (ans==0x3f3f3f3f) puts("impossible");
else cout<<ans<<endl;
return 0;
}
Kruskal
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 2*N;
int p[N];
int n,m;
struct Edge
{
int a,b,w;
}edges[M];
bool cmp(Edge A, Edge B)
{
return A.w<B.w;
}
int find(int x)
{
if (p[x]!=x) p[x] = find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for (int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w;
edges[i] ={a,b,w};
}
sort(edges,edges+m,cmp); // 先按照每条边的权重排序
for (int i=1;i<=n;i++) p[i]=i; // 初始时每个点都是独立的,没有边
int ans = 0,cnt=0;
for (int i=0;i<m;i++)
{
int a = edges[i].a;
int b = edges[i].b;
int w = edges[i].w;
a = find(a),b = find(b);
if (a!=b)
{
p[a] =b;
ans+=w;
cnt++;
}
}
if (cnt!=n-1) puts("impossible"); // 最小生成树的边数=节点数-1
else cout<<ans<<endl;
return 0;
}