题解

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 2000;
int parent[MAX_N];
int compsize[MAX_N];
struct Edge {
	int from, to, weight;
};

void init(int n) {
	for (int i = 0; i < n; i++) {
		parent[i] = i;
		compsize[i] = 1;
	}
}

int find(int a) {
	if (a == parent[a]) { return a; }
	return parent[a] = find(parent[a]);
}

bool unite(int a, int b) {
	int roota = find(a), rootb = find(b);
	if (roota == rootb) { return false; }
	if (compsize[roota] > compsize[rootb]) { swap(roota, rootb); }
	parent[roota] = rootb;
	compsize[rootb] += compsize[roota];
	return true;
}

int main() {
	int n;
	cin >> n;
	int ids[MAX_N];
	for (int i = 0; i < n; i++) { cin >> ids[i]; }
	vector<Edge> edges;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			edges.push_back({i, j, ids[i] ^ ids[j]});
		}
	}
	init(n);
	sort(edges.begin(), edges.end(),
	     [](Edge a, Edge b) { return a.weight > b.weight; });
	int eliminated = 0;
	long long ans = 0;
	for (Edge e : edges) {
		if (unite(e.from, e.to)) {
			eliminated++;
			ans += e.weight;
			if (eliminated == n - 1) {
				cout << ans << endl;
				return 0;
			}
		}
	}
}