【bzoj3943】[Usaco2015 Feb]SuperBull

2015.05.27 20:27 Wed | 15次阅读 | 旧日oi | 固定链接 | 源码

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

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;
int n;
ll ans,dis[2005],a[2005];
bool vis[2005];
void prim()
{ 
    int i,j,k;  
    for(i=1;i<=n;i++)  
    {  
        k=0;  
        for(j=1;j<=n;j++) if(!vis[j]&&dis[j]>=dis[k]) k=j;  
        vis[k]=true;ans+=dis[k];  
        for(j=1;j<=n;j++) dis[j]=max(dis[j],a[k]^a[j]);  
    }  
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    prim();
    cout<<ans<<endl;    
}```