比赛 |
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;
}