79分最小生成树求助,悬一关
查看原帖
79分最小生成树求助,悬一关
947854
ztyo_zysclown楼主2024/4/24 19:22
#include<bits/stdc++.h>
using namespace std;
const int N=520,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
	memset(dist,0x3f,sizeof(dist));
	int res=0;
	for(int i=0;i<n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[t]>dist[j])){
				t=j;
			}
		}//判断这个点对集合中的每一个点的边中最短的那一条 
		if(i&&dist[t]==INF) return INF;
		if(i) res+=dist[t];//点不能是一 
		for(int j=1;j<=n;j++){
			dist[j]=min(dist[j],g[t][j]);
		} //更新其他的点到集合的距离 
		st[t]=true;//入树 
	}
	return res;
}
int main(){
	cin>>n>>m;
	memset(g,0x3f,sizeof(g));
	while(m--){
		int u,v,m;
		cin>>u>>v>>m;
		g[u][v]=g[v][u]=min(g[u][v],m);
	}
//	for(int i=1;i<=n;i++){
//		cout<<dist[i]<<" ";
//	}
	int t=prim();
	if(t==INF){
		cout<<"orz";
		return 0;
	}
	cout<<t;
	return 0;
} 
2024/4/24 19:22
加载中...