???re5-10
查看原帖
???re5-10
1162380
liverxiwo楼主2024/4/8 13:09
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum,cnt,ans,father[2005],id[2005];
struct edge{
	int u,v,w;
}e[200005];
int find(int x){
	if(father[x]==x){
		return x;
	}
	return father[x]=find(father[x]);
}
bool cmp(const edge&x,const edge&y){
	return x.w>y.w;
}
signed main(){
	scanf("%lld",&n);
	for(register int i=1;i<=n;i++){
		scanf("%lld",&id[i]);
		father[i]=i;
	}
	for(register int i=1;i<n;i++){
		for(register int j=i+1;j<=n;j++){
			e[++sum].u=i;
			e[sum].v=j;
			e[sum].w=id[i]^id[j];
		}
	}
	sort(e+1,e+sum+1,cmp);
	for(register int i=1;i<=sum;i++){
		register int x=find(e[i].u);
		register int y=find(e[i].v);
		if(x==y){
			continue;
		}
		ans+=e[i].w;
		father[x]=y;
		cnt++;
		if(cnt==n-1){
			break;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

能过样例,一百个不理解

2024/4/8 13:09
加载中...