16分 prim算法 HELP!!!
查看原帖
16分 prim算法 HELP!!!
1268529
jiangbaolin楼主2024/10/9 17:27
#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,z,a[15001][15001],b[100001],h,c,mi,s;
int main(){
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=0x7fffffff;
		}
	}
	for(int i=1;i<=m;i++){
		cin >> x >> y >> z;
		a[x][y]=min(a[x][y],z);
		a[y][x]=min(a[y][x],z);
	}
	for(int i=1;i<=n;i++){
		b[i]=a[1][i];
		if(b[i]==0){
			b[i]=0x7fffffff;
		}
	}
	b[1]=0;
	for(int i=2;i<=n;i++){
		mi=0x7fffffff;
		for(int j=1;j<=n;j++){
			if(mi>b[j] && b[j]!=0){
				mi=b[j];
				h=j;
			}
		}
		b[h]=0;
		a[h/n+1][h%n]=0;
		a[h%n][h/n+1]=0;
		for(int j=1;j<=n;j++){
			if(b[i]!=0 && a[h%n][j]!=0){
				b[j]=min(b[j],a[h%n][j]);
			}
		}
		s=s+mi;
	}
	if(s<0x7fffffff && s!=0){
		cout << s;
	}
	else{
		cout << "orz";
	}
	return 0;
}
2024/10/9 17:27
加载中...