YONIC @ 2022-04-29 22:01:05
#include<bits/stdc++.h>
#define INF 2147483647
#define M2 (int)(5e3+3)
#define M5 ((int)(1e5+3)<<1)
using namespace std;
int n,m,ans,tot,tot2,now=1,head[M2<<1],vis[M2<<1],dis[M2<<1];
struct{int nxt,to,w;}h[M5<<1];
void add(int u,int v,int w){
h[++tot].to=v;
h[tot].nxt=head[u];
h[tot].w=w;
head[u]=tot;
}
int prim(){
for(int i=2;i<=n;++i) dis[i]=INF;
for(int i=head[1];i;i=h[i].nxt) dis[h[i].to]=min(dis[h[i].to],h[i].w);
while(++tot2<n){
int minn=INF;
vis[now]=1;
for(int i=1;i<=n;++i){
if(!vis[i]&&minn>dis[i]){
minn=dis[i];
now=i;
}
}
ans+=minn;
for(int i=head[now];i;i=h[i].nxt){
int v=h[i].to;
if(dis[v]>h[i].w&&!vis[v]) dis[v]=h[i].w;
}
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
printf("%d",prim());
return 0;
}
by Southern_Dynasty @ 2022-04-29 22:31:24
@YONIC 您特判图不连通的情况了吗
by Joseph__Joestar @ 2022-05-30 16:04:42
@暗夜黑黑黑手 数据没有图不连通的情况
by kyrie_lrving1992 @ 2022-06-07 16:43:23
你没判断orz