[文章目录]
Description
一共有N支球队参加这场比赛，每支球队都有一个特有的取值在1-2^30-1之间的整数编号(即：所有球队编号各不相同)。“犇”锦标赛是一个淘汰赛制的比赛——每场比赛过后，FJ选择一支球队淘汰，淘汰了的球队将不能再参加比赛。锦标赛在只有一支球队留下的时候就结束了。FJ发现了一个神奇的规律：在任意一场比赛中，这场比赛的得分是参加比赛两队的编号的异或(Xor)值。例如：编号为12的队伍和编号为20的队伍之间的比赛的得分是24分，因为 12(01100) Xor 20(10100) = 24(11000)。FJ相信比赛的得分越高，比赛就越好看，因此，他希望安排一个比赛顺序，使得所有比赛的得分和最高。请帮助FJ决定比赛的顺序。1<=N<=2000
我居然还在想什么拆位，什么高斯消元。。。
发现每两个队比赛的得分是亦或值，并且有n-1次比赛。如果这是一张图的话就是求一个完全图的最大生成树。
完全图的话还是邻接矩阵+prim比较好 复杂度O(n^2)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll sum;
int n,w[2017];
int map[2017][2017];
bool v[2017];
void prim()
{
memset(w,0xef,sizeof w); w[1]=0;
int tmp,k;
for(int i=1;i<n;++i)
{
tmp=0xefefefef;
for(int j=1;j<=n;++j)
if(!v[j]&&w[j]>tmp) tmp=w[j],k=j;
v[k]=1;
for(int j=1;j<=n;++j)
if(!v[j]) w[j]=max(w[j],map[k][j]);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",w+i);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
map[i][j]=w[i]^w[j];
prim();
for(int i=1;i<=n;++i) sum+=w[i];
printf("%lld",sum);
return 0;
}