最小生成树

题目传送门

解题思路

这题就是最小生成树模板
因为kruskal是O(n3)会TLE
所以我放了个prim的代码
有道题目最优布线问题（最小生成树）和这题很像

AC代码

#include<iostream>
#include<cstring>
using namespace std;
int n,n1,k,s,a[5005][5005],b[5005],m[5005];
int main()
{
   
	cin>>n>>n1;//输入
	for(int i=1;i<=n1;i++)
	{
   
		int x,y,z;
		cin>>x>>y>>z;
		if(a[x][y]!=0)a[x][y]=a[y][x]=min(a[x][y],z);
		else a[x][y]=a[y][x]=z;
	}
	memset(m,0x7f,sizeof(m));//将值弄最大
	m[1]=0;  //将第一个为0
	for(int i=1;i<=n;i++)
	{
   
		k=0;
		for(int j=1;j<=n;j++)
		 if(!b[j]&&(m[j]<m[k]))//如果这是蓝点，并且与白点相连最短，就记录
		  k=j;
		b[k]=1;//将这个为白点
		for(int j=1;j<=n;j++)
		 if(!b[j]&&(a[k][j]!=0))//如果这是蓝点，并且与这个白点的距离，比与它相连的白点的值还小，就更新
		  m[j]=min(m[j],a[k][j]);   
	}  
	for(int i=1;i<=n;i++)//加每个点的最小权值
	 if(b[i]==0){
   cout<<"orz";return 0;}
    else s+=m[i];
	cout<<s;
}

谢谢