求助
  • 板块学术版
  • 楼主Crazyouth
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/6 16:06
  • 上次更新2023/10/27 16:44:50
查看原帖
求助
766339
Crazyouth楼主2022/8/6 16:06

哪个大佬帮我看下我的prim求最小生成树哪里错了

#include <iostream>
#include <cstring>
using namespace std;
const long long inf=123456789;
int mina[5001],sum,v[5001],node[5001][5001],n,m;
void f()
{
	memset(node,inf,sizeof(node));
	for(int i=1;i<=n;i++)
	{
		node[i][i]=0;
	}
	int s,t,u;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>s>>t>>u;
		if(node[s][t]>u&&s!=t)
		node[s][t]=node[t][s]=u;
	}
	
}
void prim()
{
	int minn,k;
	for(int i=1;i<=n;i++) mina[i]=inf;
	mina[1]=0;
	v[1]=1;
	sum=0;
	for(int i=1;i<n;i++)
	{
		k=0;
		minn=inf;
		for(int j=1;j<=n;j++)
		{
			if(!v[j])
			{
				if(mina[j]<minn)
				{
					k=j;
					minn=mina[j];
				}
			}
		}
		if(!k&&i<n)
		{
			cout<<"orz";
			return;
		}
		v[k]=1;
		sum+=mina[k];
		for(int j=1;j<=n;j++)
		{
			if(!v[j])
			{
				if(node[k][j]<mina[j]) mina[j]=node[k][j];
			}
		}
	}
	cout<<sum;
	return;
}
int main()
{
	memset(v,0,sizeof(v));
	f();
	prim();
	return 0;
}
2022/8/6 16:06
加载中...