题解 P4826 【[USACO15FEB]Superbull 超级牛】

题意描述

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

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

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

求总得分的最大值

解题思路

对于每一头牛，除了最后的赢家，有且仅有一个战胜自己的牛
对于每一头牛，可能会战胜大于等于0，小于n头牛
对于最后的赢家，没有人会战胜它（这不废话吗
共有n-1场比赛

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

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

注意事项

总得分记得开long long
边的数组容量多卡点

代码

#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;
}