洛谷 P4826 [USACO15FEB]Superbull S 图论最小生成树

2023.4.1：更新抽象

又是鸽了三千万年...

--------------------------------------------------------------------

题目描述

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<=<=2000)(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.

题意翻译

Bessie和她的朋友们正在一年一度的Superbull锦标赛中打球，而Farmer John负责让比赛尽可能激动人心。总共有 N 支队伍（ 1≤N≤2000 ）参加了Superbull锦标赛。每个团队都有一个 1...230−11...230−1的团队ID。

Superbull是一场淘汰赛 - 在每场比赛之后，FJ选择淘汰其中一支球队，而被淘汰的球队再也无法参加任何比赛了。当只剩下一支球队时，比赛就结束了。

FJ注意到一个不寻常的事情：在任何游戏中，两个团队的总分是两个团队ID的按位异或（XOR）。例如，如果第 12 队和第 20 队将参加比赛，则该游戏的得分为 24 分，因为01100 XOR 10100 = 11000。

FJ想要设计一种比赛方案，让所有比赛的得分总和最大。请帮助Farmer John组织比赛。

输入格式：第一行包括一个整数 N ，下面 N 行每行包括一个队伍的ID。

输出格式：输出一个整数，代表比赛的最大总得分。

样例解释：让 3 队与 9 队进行比赛，并让 9 队晋级。然后他让 6 队和 9 队对决，让 6 队获胜。最后，第 6 队和第 10 队比赛， 10队获胜。总得分为：3 XOR 9+6 XOR 9+6 XOR 10=10+15+12=37。

输入输出样例
输入 #1
4
3
6
9
10
输出 #1
37

这题说实话，抽象起来是比较难的

但如果算法抽象正确，后面基本是模板了

一.抽象

找出题目的特点

1.淘汰赛：意味着n支队伍只有n-1次比赛，每个队伍只有一个队伍战胜自己

2.最大精彩值：每次比赛，都是在当前情况下精彩程度最高的，并且双方并未输过

两支队伍比赛，只能有一个人赢球

也就是说两个队伍中，只能有一个后面还有比赛，

输了的队伍不可能再比赛了

此时，我们很简单的能看出来是图论了，于是我们把每个队伍抽象成点，每一条边就是两队的比赛，权值为比赛总分

假设有这样四支队伍，设1赢了2,3赢了4

此时，就应该让1和3比赛了

设1赢了

那我们再加上权值（此处的权值不一定为实际题目中亦或的结果）

复杂起来了（）

此时，最大的权值是9，那就让2和3比赛，谁赢了我不知道，接着往下看

第二大是7，那么就让3和4比，基于我们上面说过的

输了的队伍不可能再比赛了

那么3肯定没输，那么2输了，其他比赛不能参加了

3和4谁赢了，我依然不知道

第三小是5，可是其中一方2已经输了，不能再比赛了

继续看，接着是权值为4，谁赢了，我不知道

然后6和4比，因为4比了两次，所以刚才的比赛4赢了，3输了

这样下来，冠军就是4，最大精彩程度为22

我们刚才的操作，每次都去寻找最大值，并且每个点都只输过一次，抽象到图里就是用最少的边联通整个图，并且权值还得最大，很明显就是最大生成树，改一下排序顺序

于是，AC代码就这么出来了：

# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
# define int long long
int n,m,sum;
int id[2005];
int f[2005];
void make(){
	for (int i=1;i<=n;i++){
		f[i]=i;
	}
}
int find(int x){
	if (f[x]!=x){
		return f[x]=find(f[x]);
	}
	return f[x];
}
struct node{
	int u,v,w;
}e[2005*2005];
void add(int u,int v,int w){
	m++;
	e[m].u=u;
	e[m].v=v;
	e[m].w=w;
}
bool cmp(node x,node y){
	return x.w>y.w;
}
void kruskal(){
	make();
	int cnt=0;
	sort(e+1,e+1+m,cmp);
	for (int i=1;i<=m;i++){
		int a=find(e[i].u),b=find(e[i].v);
		if (a==b){
			continue;
		}
		f[b]=a;
		cnt++;
		sum+=e[i].w;
		if (cnt==n-1){
		    return ;
		}
	}
}
signed main(){
	scanf("%lld",&n);
	for (int i=1;i<=n;i++){
		scanf("%lld",&id[i]);
	}
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			add(i,j,id[i]^id[j]);
		}
	}
	kruskal();
	printf("%lld",sum);
	return 0;
}