记录编号	159733	评测结果	AAAAAAAAAA
题目名称	1941.[USACO Feb15 Gold] Superbull	最终得分	100
用户昵称	fyb	是否通过	通过
代码语言	C++	运行时间	0.193 s
提交时间	2015-04-22 16:05:05	内存使用	0.34 MiB

#include <stdio.h>
#include <queue>

using namespace std;

#define NMAX 2000
#define VERY_LARGE 2000000000ll

struct node{
	int ind;
	long long d;

	bool operator < (const node b)const{return d<b.d;}
};

int m[NMAX];
bool done[NMAX];
int fa[NMAX];
long long d[NMAX];
priority_queue<node> q;

int main(){
	int n;
	node tn;
	long long ans=0;
	int i;

	freopen("superbull.in","r",stdin);
	freopen("superbull.out","w",stdout);

	scanf("%d",&n);
	getchar();
	for(i=0;i<n;i++){
		scanf("%d",m+i);
		getchar();
	}

	tn.ind=0;
	tn.d=d[0]=VERY_LARGE;
	q.push(tn);

	for(i=0;i<n;i++)fa[i]=-1;

	while(!q.empty()){
		tn=q.top();
		q.pop();
		if(done[tn.ind])continue;
		else done[tn.ind]=true;
		for(i=0;i<n;i++)
			if((!done[i])&&(m[tn.ind]^m[i])>d[i]){
				fa[i]=tn.ind;
				d[i]=m[tn.ind]^m[i];
				q.push((node){i,d[i]});
			}
	}

	for(i=0;i<n;i++)if(fa[i]!=-1)ans+=m[i]^m[fa[i]];
	printf("%lld",ans);
	return 0;
}