求助!实在找不到错哪里了
查看原帖
求助!实在找不到错哪里了
825876
Peaceful_Evening楼主2023/10/16 23:19

rt。第二个样例点就过不去,输出为4。可能是我现在脑子比较糊,或者实力还不够,有哪位大佬能帮我看一下吗?

#include <bits/stdc++.h>
using namespace std;
struct s {
	int u;
	int v;
	int w;
} a[5005];
int fa[10001];
int sum,ans,cnt;
bool cmp(s x,s y) {
	return x.w<y.w;
}
void build(int x,int y,int z){
	sum++;
	a[sum].u=x;
	a[sum].v=y;
	a[sum].w=z;
}
int find(int x) {
	if(fa[x]!=x) {
		fa[x]=find(fa[x]);
	}
	return fa[x];
}
void unionn(int x,int y) {
	int pa=find(x);
	int pb=find(y);
	if(pa!=pb) {
		fa[pa]=pb;
	}
}
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		for(int j=1; j<=m; j++) {
			int x;
			cin>>x;
			if(x!=0&&i<j) {
				build(i,j,x);
			}

		}
	}
	
	for(int i=1;i<=m;i++){
	    fa[i]=i;
		build(0,i,n);
	}
	sort(a+1,a+sum+1,cmp);
	for(int i=1;i<=sum;i++){
		if(find(a[i].u)!=find(a[i].v)){
		ans+=a[i].w;
			unionn(a[i].u,a[i].v);
			
			cnt++;
		}
		if(cnt==m-1){
			break;
		}
	}
	cout<<ans;
	return 0;
}

2023/10/16 23:19
加载中...