Superbull（最大生成树）（Kruskal）-白红宇

Superbull（最大生成树）（Kruskal）

阅读量：6848 次

发布时间：2019-06-26

本文共 3010 字，大约阅读时间需要 10 分钟。

Superbull

时间限制: 1 Sec 内存限制: 64 MB

提交: 49 解决: 13

[][][]

题目描述

Bessie and her friends are playing hoofball in the annual Superbull championship, and Farmer John is in charge of making the tournament as exciting as possible. A total of N (1 <= N <= 2000) teams are playing in the Superbull. Each team is assigned a distinct integer team ID in the range 1...2^30-1 to distinguish it from the other teams. The Superbull is an elimination tournament -- after every game, Farmer John chooses which team to eliminate from the Superbull, and the eliminated team can no longer play in any more games. The Superbull ends when only one team remains.

Farmer John notices a very unusual property about the scores in matches! In any game, the combined score of the two teams always ends up being the bitwise exclusive OR (XOR) of the two team IDs. For example, if teams 12 and 20 were to play, then 24 points would be scored in that game, since 01100 XOR 10100 = 11000.

Farmer John believes that the more points are scored in a game, the more exciting the game is. Because of this, he wants to choose a series of games to be played such that the total number of points scored in the Superbull is maximized. Please help Farmer John organize the matches.

输入

The first line contains the single integer N. The following N lines contain the N team IDs.

输出

Output the maximum possible number of points that can be scored in the Superbull.

样例输入

样例输出

提示

OUTPUT DETAILS: One way to achieve 37 is as follows: FJ matches teams 3

and 9, and decides that 9 wins, so teams 6, 9, and 10 are left in the

tournament. He then matches teams 6 and 9, and lets team 6 win. Teams 6

and 10 are then left in the tournament. Finally, teams 6 and 10 face

off, and team 10 wins. The total number of points scored is (3 XOR 9) +

(6 XOR 9) + (6 XOR 10) = 10 + 15 + 12 = 37.

NOTE: The bitwise exclusive OR operation, commonly denoted by the ^

symbol, is a bitwise operation that performs the logical exclusive OR

operation on each position in two binary integers. The result in each

position is 1 if only the first bit is 1 or only the second bit is 1,

but is 0 if both bits are 0 or both are 1. For example: 10100 (decimal

20) XOR 01100 (decimal 12) = 11000 (decimal 24)

【分析】最大生成树，模板题

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include
                     
                      #define mod 1000000007#define inf 0x3f3f3f3f#define pi acos(-1.0)using namespace std;typedef long long ll;const int N=2005;const int M=15005;struct Edg { int v,u; ll w;} edg[4000010];bool cmp(Edg g,Edg h) { return g.w>h.w;}int n,m,maxn,cnt;int parent[N];int a[N];void init() { for(int i=0; i
                      
                       =n-1) { printf("%lld\n",sum); break; } }}int main() { scanf("%d",&n); cnt=-1; init(); Build(); Kruskal(); return 0;}

View Code

转载于:https://www.cnblogs.com/jianrenfang/p/5791125.html

你可能感兴趣的文章