[bzoj3943][Usaco2015 Feb]SuperBull_Kruskal
2024-09-04 04:42:55
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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#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("Fuck %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;
}
小结:有意思...
最新文章
- vmware里面的名词 vSphere、vCenter Server、ESXI、vSphere Client
- hibernate中数据库方言
- CentOS 程序开机自启动方法总结
- MAC 安装 Protobuf
- [IoC]6 详解@Autowired、@Qualifier和@Required
- C#中判断文件夹中存在某个txt文本
- FastJSON学习
- JS获取页面上所有input
- 单机Hadoop搭建
- Postgres中的物化节点之sort节点
- macOS Mojave配置OpenGL开发环境
- MySQL系列--1.安装卸载与用户权限管理
- (三)ajax请求不同源之服务器代理跨域
- WORLD 文件选择的操作方法
- Spark GraphX快速入门
- bzoj 4328 始祖鸟
- 云计算--hdfs dfs 命令
- Java并发包学习一 ThreadFactory介绍
- PL/SQL Developer的安装以及与64位Oracle Database进行连接
- [APP] Android 开发笔记 001-环境搭建与命令行创建项目