Prime邻接表算法,16分求助QwQ
查看原帖
Prime邻接表算法,16分求助QwQ
343245
Bigfish_楼主2022/7/27 21:55
#include <bits/stdc++.h>
using namespace std;
int n,m,minn[5010],f[5005][5005],u,v,minmax1=0;
int l=0;//计数器 
long long MST=0;
bool b[5010];//蓝白点 
inline int read()//快读
{
	int x=0,j=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') j=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*j;
}
int main()
{
	n=read();m=read();
	if(m<n-1)//特判优化? 
	{
		printf("orz");
		return 0;
	}
	for(int t=1;t<=n;++t)//初始化f 
		for(int i=1;i<=n;++i)
			f[t][i]=INT_MAX;
	for(int t=0;t<=n;++t)//初始化minn 
		minn[t]=INT_MAX;
	for(int t=1;t<=m;++t)
	{
		int x=read(),y=read(),z=read();
		if(f[x][y]!=0&&f[x][y]<=z) ;//不赋值 
		else 
		{
			f[x][y]=z;
			f[y][x]=z;
		}
	}
	minn[1]=0;
	b[1]=0;//标记为蓝点=w= 
	for(int t=1;t<=n;++t)//枚举所有的点
	{
		minmax1=0;
		for(int i=1;i<=n;++i)//找距离最小的蓝点 
		{
			if(b[i]==0&&minn[i]<minn[minmax1])
			{
				minmax1=i;
			}
		}
		if(minmax1==0) break;//找不到代表图不连通,优化? 
		b[minmax1]=1;//标记为白点
		MST+=minn[minmax1];
		++l;//记录白点个数
		for(int i=1;i<=n;++i) 
		{
			if(b[i]==0&&f[minmax1][i]!=INT_MAX&&minn[i]>minn[minmax1]+f[minmax1][i])
			{
				minn[i]=minn[minmax1]+f[minmax1][i];//更新minn数组 
			}
		}
	} 
	if(l==n)
		printf("%d",MST);
	else 
		printf("orz");
	return 0;
 } 
2022/7/27 21:55
加载中...