Prim
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010,INF=0x3f3f3f3f;
int n,m;
int a,b,c;
int g[N][N],dist[N];
bool st[N];
int Prim()
{
memset(dist,0x3f,sizeof dist);
int res=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]=1;
if(i) res+=dist[t];
for(int j=1;j<=n;++j) dist[j]=min(dist[j],g[t][j]);
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=c;
}
printf("%d\n",Prim());
return 0;
}
Kruskal
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,m;
int a,b,c;
int p[N];
struct Edge
{
int a,b,c;
bool operator < (const Edge &C)
{
return c<C.c;
}
}edges[N];
int find(int x)
{
if(x!=p[x]) p[x]=find(p[x]);
else return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;++i) p[i]=i;
for(int i=0;i<m;++i)
{
scanf("%d%d%d",&a,&b,&c);
edges[i].a=a,edges[i].b=b,edges[i].c=c;
}
int res=0;
sort(edges,edges+m);
for(int i=0;i<m;++i)
{
a=edges[i].a,b=edges[i].b;
a=find(a),b=find(b);
if(a!=b)
{
p[a]=b;
res+=edges[i].c;
}
}
printf("%d\n",res);
return 0;
}