自动搬运

查看原文

来自洛谷，原作者为

	Register **

搬运于2025-08-24 22:04:21，当前版本为作者最后更新于2019-04-22 19:05:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意描述

有$n$头牛比赛，每场比赛都选任意两头牛

每场比赛会影响总得分，总得分会加上选手$x$的$id$和选手$y$的$id$按位异或的值

每局比赛你都要钦定一头牛输掉，输掉的牛不能继续比赛

求总得分的最大值

解题思路

• 对于每一头牛，除了最后的赢家，有且仅有一个战胜自己的牛

• 对于每一头牛，可能会战胜大于等于$0$，小于$n$头牛

• 对于最后的赢家，没有人会战胜它（这不废话吗

• 共有$n-1$场比赛

以上四点，分别与树的父亲结点、儿子结点、根结点、边的数量对应

我们可以预处理出每两头牛对局的得分，跑一次最大生成树即可

注意事项

• 总得分记得开long long

• 边的数组容量多卡点

• $C++$中^是异或的意思，不是幂运算

代码

#include <cstdio>
#include <algorithm>
int n,sum,cnt,ans,a[2001],f[2001];
struct edge{
	int u,v,c;
}e[2000000];
int read(){
    char ch=getchar();int res=0,w=1;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {res=res*10+ch-'0';ch=getchar();}
    return res*w;
}
int Find(int x){
	if(f[x]==x) return x;
	return f[x]=Find(f[x]);
}
inline bool comp(const edge&x,const edge&y){
	return x.c>y.c;
}
int main(){
	n=read();
	for(register int i=1;i<=n;i++) {a[i]=read();f[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].c=a[i]^a[j];}
	std::sort(e+1,e+sum+1,comp);
	for(register int i=1,x1,x2;i<=sum;i++)
	{
		x1=Find(e[i].u);x2=Find(e[i].v);
		if(x1==x2) continue;
		ans+=e[i].c;f[x1]=x2;cnt++;
		if(cnt==n-1) break;
	}
	printf("%d\n",ans);
    return 0;
}