比赛 20150420 评测结果 AWWWWWWWWW
题目名称 超牛冠军赛 最终得分 10
用户昵称 清羽 运行时间 1.561 s
代码语言 C++ 内存使用 0.33 MiB
提交时间 2015-04-20 11:27:32
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn=2000;

struct Edge{
	int from,to,dist;
	
	bool operator <(const Edge& x) const{
		return dist>x.dist;
	}
	Edge(int u,int v,int w):from(u),to(v),dist(w) {}
};

char buf[40];
vector<Edge> edges;
int n,w[maxn],p[maxn];

template<class T> inline bool getd(T& x)
{
	int ch=getchar();
	bool neg=false;
	while(ch!=EOF && ch!='-' && !isdigit(ch)) ch=getchar();
	if(ch==EOF) return false;
	if(ch=='-'){
		ch=getchar();
		neg=true;
	}
	x=ch-'0';
	while(isdigit(ch=getchar())) x=x*10+ch-'0';
	if(neg) x=-x;
	return true;
}

template<class M> inline void putd(M x)
{
	int p=0;
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x==0) buf[p++]=0;
	while(x){
		buf[p++]=x%10;
		x/=10;
	}
	for(int i=p-1;i>=0;i--) putchar(buf[i]+'0');
}

int getfather(int x){ return p[x]==x?x:p[x]=getfather(p[x]); }

void init()
{
	getd(n);
	for(int i=0;i<n;i++) getd(w[i]);
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++) 
			edges.push_back(Edge(i,j,w[i]^w[j]));
}

void work()
{
	for(int i=0;i<n;i++) p[i]=i;
	sort(edges.begin(),edges.end());
	int cnt=0,ans=0;
	
	for(int i=0;i<edges.size();i++){
		Edge e=edges[i];
		int x=getfather(e.from),y=getfather(e.to);
		if(x==y) continue;
		p[x]=y;	
		ans+=e.dist;
		if(++cnt==n-1) break;
	}
	putd(ans);
}

int main()
{
	freopen("superbull.in","r",stdin);
	freopen("superbull.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}