Prim写炸了
查看原帖
Prim写炸了
557935
NaCl_ender楼主2021/11/13 22:15

想写个Prim(还没判不连通),但就算是联通图也炸了几个点,求调

#include <iostream>

#include <vector>

using namespace std;

struct Edge
{
	int v,w;
};

const int INF = 1e9;
vector<Edge> g[5010];
int n,sum; 
int mincount[5010];//mincount从最小生成树内的顶点到暂时不在最小生成树内的顶点的最小边权 

void Prim()
{
	int i,j;
	mincount[1] = 0; ////将1加入最小生成树
	for(i = 0;i < g[1].size();i++) mincount[g[1][i].v] = g[1][i].w;
	for(i = 1;i <= n - 1;i++) //除点1外,枚举最小生成树剩下的n - 1条边 
	{
		int minn = INF,num;
		for(j = 1;j <= n;j++) //枚举剩余的点 
		{
			if(mincount[j] != 0&&mincount[j] < minn) //集合外的点mincount不等于0 
			{
				minn = mincount[j];
				num = j;
			}
		}
		mincount[num] = 0; //将num加入最小生成树
		sum+=minn;
		for(j = 0;j < g[num].size();j++) mincount[g[num][j].v] = min(mincount[g[num][j].v],g[num][j].w);
	}
}

int main()
{
	int m,i;
	cin>>n>>m;
	for(i = 1;i <= n;i++) mincount[i] = INF;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back((Edge){v,w});
		g[v].push_back((Edge){u,w});
	}
	Prim();
	cout<<sum;
	return 0;
}
2021/11/13 22:15
加载中...