比赛 20150420 评测结果 AAAAAAAAAA
题目名称 超牛冠军赛 最终得分 100
用户昵称 Satoshi 运行时间 0.287 s
代码语言 C++ 内存使用 14.05 MiB
提交时间 2015-04-20 11:07:17
显示代码纯文本
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("superbull.in");
ofstream out("superbull.out");
int n,sato[2001]={0};
int w[2001][2001]={0};
long long ans=0;
int p[2001]={0};
int key[2001]={0};
int prim()
{
	int inq[10001],i,j,u=0,v;
	i=j=1;
	for(i=1;i<=n;i++)
	{
		p[i]=0;
		inq[i]=0;
		key[i]=9999999;
	}
	key[1]=0;
	for(j=1;j<=n;j++)
	{
		u=0;key[u]=9999999;
		for(i=1;i<=n;i++)
		{
			if(inq[i]==0&&key[i]<key[u])u=i;
		}
		//out<<u<<endl;
		inq[u]=1;ans+=key[u];
		for(v=1;v<=n;v++)
	    {
		    if(w[u][v]!=0&&inq[v]==0&&w[u][v]<key[v])
		    {
			    p[v]=u;
		        key[v]=w[u][v];
		    }
	    }
	}
	return 0;
}
int main()
{
	int i,j,k,ac;
	in>>n;
	for(i=1;i<=n;i++)in>>sato[i];
	sort(sato+1,sato+n+1);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			w[i][j]=0;
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			ac=sato[i]^sato[j];
			w[i][j]=w[j][i]=-ac;
		}
	}
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			out<<w[i][j]<<' ';
		}
		out<<endl;
	}*/
	prim();
	out<<-ans<<endl;
	return 0;
}