SuperBull bzoj-3943 Usaco-2015 Feb

题目大意：贝西和她的朋友们在参加一年一度的“犇”(足)球锦标赛。FJ的任务是让这场锦标赛尽可能地好看。一共有N支球队参加这场比赛，每支球队都有一个特有的取值在1-230-1之间的整数编号(即：所有球队编号各不相同)。“犇”锦标赛是一个淘汰赛制的比赛——每场比赛过后，FJ选择一支球队淘汰，淘汰了的球队将不能再参加比赛。锦标赛在只有一支球队留下的时候就结束了。FJ发现了一个神奇的规律：在任意一场比赛中，这场比赛的得分是参加比赛两队的编号的异或(Xor)值。例如：编号为12的队伍和编号为20的队伍之间的比赛的得分是24分，因为 12(01100) Xor 20(10100) = 24(11000)。FJ相信比赛的得分越高，比赛就越好看，因此，他希望安排一个比赛顺序，使得所有比赛的得分和最高。请帮助FJ决定比赛的顺序

注释：$1\le N \le 2,000$。

想法：显然，最后的情况一定是一棵树。反证法：假设最后情况不是一棵树。那么一定存在这样的一条边，开始的时候是一个森林，这条边在一棵树内，使得形成环。因为每一次比赛就会淘汰一个人，k-1场比赛淘汰k-1个人，所以这棵树上只有一个点，又因为每个人不能有自环，矛盾。

所以，最后的情况一定是一棵树。

这样的话我们用两个点的点权异或值在表示这两点之间的边权，然后跑kruskal即可。

最后，附上丑陋的代码... ...

#include

#include

#include

#include

#define N 2010

using namespace std;

typedef long long ll;

struct Node

{

int a,b,val;

}f[N*N];

int fa[N],a[N];

inline bool cmp(const Node &a,const Node &b)

{

return a.val>b.val;

}

int find(int x)

{

return fa[x]==x?x:(fa[x]=find(fa[x]));

}

inline bool merge(int x,int y)

{

x=find(x); y=find(y);

if(x==y) return true;

fa[x]=y; return false;

}

int main()

{

int n; cin >> n ;

for(int i=1;i<=n;i++) fa[i]=i;

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

int cnt=0;

for(int i=1;i<=n;i++)

{

for(int j=i+1;j<=n;j++)

{

f[++cnt].a=i; f[cnt].b=j;

f[cnt].val=a[i]^a[j];

}

}

sort(f+1,f+cnt+1,cmp);

// for(int i=1;i<=cnt;i++)

// {

// printf("*** %d %d %d\n",f[i].a,f[i].b,f[i].val);

// }

int count=0;

ll ans=0;

for(int i=1;i<=cnt;i++)

{

if(!merge(f[i].a,f[i].b))

{

count++;

ans+=f[i].val;

// printf("Bitch %d\n",i);

}

if(count==n-1) break;

}

printf("%lld\n",ans);

return 0;

}

小结：有意思...