1705: 数据结构-最小生成树 prim算法 附一个问题

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1001][1001];
int parent[1001];
int minist[1001],u;
int judge[1001]={0};
int minn(int judge[],int minist[])
{
	u=999999;//请问大佬为什么INT_Max不行
	int y;
	for(int i=1;i<=n;i++)
	{	
		if(judge[i]==0&&minist[i]<u)
		{
		
			u=minist[i];
			y=i;	
		}
	
	}
	return y;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
		}
		minist[i]=99999;
		parent[i]=-1;
	}
	minist[1]=0;
	parent[1]=-1;
	int temp=1,cost=0;
	for(int i=1;i<=n;i++)
	{
		temp=minn(judge,minist);
		
	//	cout<<temp<<endl;
		judge[temp]=1;
		for(int j=2;j<=n;j++)
		{
			if(a[temp][j]<minist[j]&&judge[j]==0&&a[temp][j]!=0) 
			{
				minist[j]=a[temp][j];
				parent[j]=temp;
			}
		}	
	//	cout<<minist[temp]<<endl;
		cost+=minist[temp];
	}
	cout<<cost<<endl;
	return 0;
}