#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1005;
int n,m,ans;
int fa[maxn];
struct edge{
int x,y,v;
}e[maxn*maxn];
int find(int x) //查找父亲节点
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
bool cmp(struct edge a,struct edge b)
{
return a.v<b.v;
}
void kruskall()
{
int cnt=0;
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
if(cnt==n-1) break;
int fx=find(e[i].x);
int fy=find(e[i].y);
if(fx!=fy)
{
fa[fx]=fy; //合并两棵树
cnt++;
ans+=e[i].v;
}
}
printf("%d",ans);
}
int main()
{
int x,y,a;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&a);
e[i].x=x;
e[i].y=y;
e[i].v=a;
}
kruskall();
return 0;
}
Prim
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1005;
int n,m,ans,cnt=1;
int fa[maxn],head[maxn],dis[maxn],vis[maxn];
struct edge{
int x,y,v,next;
}e[maxn*maxn];
void addedge(int x,int y,int a)//邻接矩阵
{
e[cnt].x=x;
e[cnt].y=y;
e[cnt].v=a;
e[cnt].next=head[x];
head[x]=cnt++;
}
void primm()
{
int mi;
memset(dis,inf,sizeof(dis));
dis[1]=0;
int u;
for(int i=1;i<=n;i++)
{
mi=inf;
for(int j=1;j<=n;j++)
if(!vis[j]&&mi>dis[j])
{
mi=dis[j];u=j;
}
vis[u]=1;
ans+=mi;
for(int k=head[u];k!=-1;k=e[k].next)
{
if(dis[e[k].y]>e[k].v)
dis[e[k].y]=e[k].v;
}
}
printf("%d",ans);
}
int main()
{
int x,y,a;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&a);
addedge(x,y,a);
addedge(y,x,a);
}
primm();
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1005;
int n
,m,ans,cnt=1;
int fa[maxn],head[maxn],dis[maxn],vis[maxn];
struct edge{
int x,y,v,next;
}e[maxn*maxn];
void addedge(int x,int y,int a)//邻接矩阵
{
e[cnt].x=x;
e[cnt].y=y;
e[cnt].v=a;
e[cnt].next=head[x];
head[x]=cnt++;
}
void primm()
{
int mi;
memset(dis,inf,sizeof(dis));
dis[1]=0;
int u;
for(int i=1;i<=n;i++)
{
mi=inf;
for(int j=1;j<=n;j++)
if(!vis[j]&&mi>dis[j])
{
mi=dis[j];u=j;
}
vis[u]=1;
ans+=mi;
for(int k=head[u];k!=-1;k=e[k].next)
{
if(dis[e[k].y]>e[k].v)
dis[e[k].y]=e[k].v;
}
}
printf("%d",ans);
}
int main()
{
int x,y,a;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&a);
addedge(x,y,a);
addedge(y,x,a);
}
primm();
return 0;
}