求助,prim16分
查看原帖
求助,prim16分
1125129
WJX120423楼主2024/4/13 09:40
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y,z;
}a[200010];
int n,m,ans=0;
vector<int> v;//在生成树中的点 
bool vis[5010];
void prim(){
	memset(vis,false,sizeof(vis));
	vis[1]=true;
	v.push_back(1);
	int cnt;
	for(int i=1;i<=m;i++){
		int minnum=INT_MAX;//最近点的长度
		int minwho;//最近点是哪个
		bool flag=false;
		for(int j=0;j<v.size();j++){
			if((a[i].x==v[j]||a[i].y==v[j])&&vis[i]!=true){
				if(a[i].z<minnum){
					flag=true;
					minnum=a[i].z;
					minwho=i;
				}
			}
		}
		if(flag==true){
			ans+=minnum;
			vis[minwho]=true;
			v.push_back(minwho);
		}else{
			cout<<"orz";
			return;
		}	
	}
	cout<<ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	prim();
	return 0;
}
2024/4/13 09:40
加载中...