爆WA求助
查看原帖
爆WA求助
752094
MornHus楼主2023/3/16 13:37
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0;
	int f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
int n,cnt;
struct lines{
	int u,v,val;
}line[1999010];
int team[2001];
int f[2001];
int find(int a){
	if(f[a]!=a)f[a]=find(f[a]);
	return f[a];
}
void unions(int a,int b){
	a=find(a);
	b=find(b);
	if(a==b)return;
	else f[a]=b;
}

bool cmp(lines a,lines b){
	return a.val>b.val;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		f[i]=i;
		team[i]=read();
		for(int j=1;j<=i-1;j++){
			line[++cnt].u=i;
			line[cnt].v=j;
			line[cnt].val=team[i]^team[j];
		}	
	}
	sort(line+1,line+n+1,cmp);
	int ans=0;
	int tot=0;
	for(int i=1;i<=cnt;i++){
		if(find(line[i].u)!=find(line[i].v)){
			tot++;
			unions(line[i].u,line[i].v);
			ans+=line[i].val;
			if(tot==n-1)break;
		}
	}
	cout<<ans;
	return 0;
}
2023/3/16 13:37
加载中...