社区讨论
求助!!最小生成树模板
学术版参与者 12已保存回复 20
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 20 条
- 当前快照
- 1 份
- 快照标识符
- @mi6yrs11
- 此快照首次捕获于
- 2025/11/20 13:01 4 个月前
- 此快照最后确认于
- 2025/11/20 15:36 4 个月前
40分,不知道哪错了,求助大佬们~
CPP#include<bits/stdc++.h>//Prim算法
using namespace std;
const int Maxn=1e6+1;
int n,m,cnt,ans,tot,now=1;
int h[Maxn];
int dis[Maxn];
int vis[Maxn];
struct Skeleton
{
int nxt,to,d;
}edg[Maxn<<1];
inline void read(int &num)
{
int s=1,res=0;
char in=getchar();
while(!isdigit(in))
{
if(in=='-')
{
s=-1;
}
in=getchar();
}
while(isdigit(in))
{
res=(res<<1)+(res<<3)+in-'0';
in=getchar();
}
num=res*s;
}
inline void build(int ogn,int dtn,int len)
{
edg[++cnt].nxt=h[ogn];
edg[cnt].to=dtn;
edg[cnt].d=len;
h[ogn]=cnt;
}
inline void Prim()
{
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
for(int i=h[1];i;i=edg[i].nxt)
{
int go=edg[i].to;
dis[go]=min(dis[go],edg[i].d);
}
while(++tot<n)
{
int minn=0x7f;
vis[now]=1;
for(int i=1;i<=n;i++)
{
if(!vis[i]&&dis[i]<minn)
{
minn=dis[i];
now=i;
}
}
ans+=minn;
for(int i=h[now];i;i=edg[i].nxt)
{
int go=edg[i].to;
if(!vis[go]&&edg[i].d<dis[go])
{
dis[go]=edg[i].d;
}
}
}
}
int main()
{
//scanf("%d %d",&n,&m);
read(n),read(m);
for(int i=1;i<=m;i++)
{
int u,v,dist;
//scanf("%d %d %d",&u,&v,&dist);
read(u),read(v),read(dist);
build(u,v,dist);
build(v,u,dist);
}
Prim();
printf("%d\n",ans);
return 0;
}
回复
共 20 条回复,欢迎继续交流。
正在加载回复...