prim求助,悬关
查看原帖
prim求助,悬关
740254
To_2051楼主2024/3/17 17:20

全部输出orz

#include<bits/stdc++.h>
using namespace std;
int closest[100001],lowcost[10001];
int Inf=0x3f3f3f3f;
bool vis[100001];
struct node{
	int to,w;
};
int n,ans;
vector<node> e[100001];
bool prim(int u){
	memset(lowcost,127,sizeof(lowcost));
	lowcost[u]=0;
	for(int i=1;i<=n;i++) closest[i]=-1;
	closest[u]=u;
	for(int f=1;f<=n;f++)
	{
		int t=-1,minc=Inf;
		for(int i=1;i<=n;i++)
			if(lowcost[i]<minc&&vis[i]==0)
				minc=lowcost[i],t=i;
		if(t==-1) return 0;
		vis[t]=1;
		ans+=lowcost[t];
		for(auto v:e[t])
			if(lowcost[v.to]>v.w&&!vis[v.to])
				lowcost[v.to]=v.w,closest[v.to]=t;
	}
}
int main()
{
	int m,u,v,w,minn,t;
	memset(lowcost,127,sizeof(lowcost));
	lowcost[1]=0;
	closest[1]=1;
	vis[1]=1;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});
	}
	if(prim(1)) cout<<ans<<endl;
	else cout<<"orz";
	return 0;
}

2024/3/17 17:20
加载中...