社区讨论

3个点RE,求dalao救

P1194买礼物参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi6vytc4
此快照首次捕获于
2025/11/20 11:43
4 个月前
此快照最后确认于
2025/11/20 11:43
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>

using namespace std;

struct node{
	int x,y,w;
}a[250000];
int A[501];
int d[501];
bool cmp(node p,node q){
	return p.w<q.w;
}
int n,m;
int anc(int x){
	if(A[x]==x){
		return x;
	}
	else{
		A[x]=anc(A[x]);
		return A[x];
	}
}
void uni(int x,int y){
	if(d[x]>=d[y]){
		A[y]=x;
		d[x]=max(d[x],d[y]+1);
	}
	else{
		A[x]=y;
		d[y]=max(d[y],d[x]+1);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int e=0;
	for(int i=1;i<=m;i++){
		A[i]=i;
		d[i]=1;
	}
	for(int i=0;i<m;i++){
		for(int j=0;j<m;j++){
			int 
			
			scanf("%d",&b);
			if(i!=j){
				if(b!=0&&b<n){
					a[e].x=i;
					a[e].y=j;
					a[e].w=b;
					e++;
					a[e].x=j;
					a[e].y=i;
					a[e].w=b;
					e++;
				}
				else{
					a[e].x=i;
					a[e].y=j;
					a[e].w=n;
					e++;
					a[e].x=j;
					a[e].y=i;
					a[e].w=n;
					e++;
				}
			}
		}
	}
	sort(a,a+e,cmp);
	int E=0,ans=n;
	for(int i=0;E<m-1;i++){
		int xx=anc(a[i].x),yy=anc(a[i].y);
		if(xx!=yy){
			uni(xx,yy);
			ans+=a[i].w;
			E++;
		}
	}
	printf("%d",ans);
	return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...