USACO2015FEB SILVER Superbull

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Sun Oct 28 21:08:29 CST 2018

In Category: NoCategory

Description：

一场比赛 $n$ 个队伍，每次两个队伍比赛选一个留下，这场比赛的得分为两个队伍权值的异或值，选择每次参赛的队伍以及胜负情况使得所有比赛的得分之和最大。

$1\leqslant n\leqslant 2000$

Solution：

一个很有意思的东西， $n$ 个东西，每次选出来两个删掉一个，最后的关系会形成一棵树。

知道了这个这题就是一个裸的最大生成树了，因为是完全图所以用 $prim$ 复杂度 $O(n^2)$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 2010

int w[MAXN];

struct edge

{

	int to,nxt,v;

}e[MAXN * MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	return;

}

int dis[MAXN];

bool v[MAXN];

int main()

{

	scanf("%d",&n);

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

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

	{

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

		{

			if(i == j)continue;

			add(i,j,w[i] ^ w[j]);

		}

	}

	memset(dis,0xc0,sizeof(dis));

	memset(v,false,sizeof(v));

	dis[1] = 0;

	long long ans = 0;

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

	{

		int k = 0;

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

		{

			if(!v[i] && dis[i] > dis[k])

			{

				k = i;

			}

		}

		v[k] = true;

		ans += dis[k];

		dis[k] = 0xc0c0c0c0;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(!v[e[i].to] && dis[e[i].to] < e[i].v)

			{

				dis[e[i].to] = e[i].v;

			}

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: 图论-prim

wjh15101051