比较需要观察的题。
设 \(v\) 为所有边权异或和。直觉是设一条未确定权值的边边权为 \(v\)，其他的为 \(0\) 最优。证明大概就是讨论 MST 是否全部使用未确定权值的边。若全使用了，那么根据 \(\oplus w \le \sum w\) 可知 \(\min \sum w = \oplus w\)，并且在 \(w\) 两两按位与均为 \(0\) 时取等；若没有全使用，可以把没使用的赋成 \(v\)，其他全赋成 \(0\)。
发现若补图存在环，我们只要把一条构成环的边边权设为 \(v\) 即可，显然它会被环上其他边替代。补图存在环的一个必要条件是 \(m < \frac{n(n - 1)}{2} - n + 1\)，因为补图边数 \(\ge n\)。这种情况下，我们先求出补图连通块，将他们作为边权为 \(0\) 的边在并查集上 merge 起来，再做一遍 Kruskal 即可。至于如何求补图连通块，这是个典题，可以考虑暴力 + 链表（并查集），具体见此。这部分时间复杂度 \(O(m \log m + (n + m) \log n)\)。
若 \(m \ge \frac{n(n - 1)}{2} - n + 1\)，此时补图边数 \(< n\)，又因为 \(m\) 是 \(O(n^2)\) 级别，因此 \(n\) 是 \(O(\sqrt{m})\) 的。此时可以直接暴力枚举将补图的哪条边边权设为 \(v\)，再做 Kruskal 即可。这部分时间复杂度 \(O(m \sqrt{m} \log n)\)，实际用时不多。
code
// Problem: C. Complete the MST
// Contest: Codeforces - Codeforces Round 715 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1508/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 200100;
ll n, m, fa[maxn];
struct E {
ll u, v, d;
} G[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
return 1;
} else {
return 0;
}
}
namespace Sub1 {
void solve() {
ll s = 0;
for (int i = 1; i <= m; ++i) {
s ^= G[i].d;
}
set<pii> st;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
st.insert(make_pair(i, j));
}
}
for (int i = 1; i <= m; ++i) {
int u = G[i].u, v = G[i].v;
if (u > v) {
swap(u, v);
}
st.erase(make_pair(u, v));
}
ll ans = 1e18;
for (pii e : st) {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
}
for (pii p : st) {
if (e != p) {
merge(p.fst, p.scd);
}
}
ll res = 0;
bool flag = 0;
for (int i = 1; i <= m; ++i) {
int u = G[i].u, v = G[i].v, d = G[i].d;
if (s <= d && !flag) {
flag = 1;
if (merge(e.fst, e.scd)) {
res += s;
}
}
if (merge(u, v)) {
res += d;
}
}
ans = min(ans, res);
}
printf("%lld\n", ans);
}
}
namespace Sub2 {
bool vis[maxn];
set<int> S[maxn];
struct DSU {
int fa[maxn];
inline void init() {
for (int i = 1; i <= n + 1; ++i) {
fa[i] = i;
}
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
} D;
void dfs(int u) {
vis[u] = 1;
D.fa[u] = u + 1;
for (int v = D.find(1); v <= n; v = D.find(v + 1)) {
if (S[u].find(v) == S[u].end()) {
merge(u, v);
dfs(v);
}
}
}
void solve() {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
}
D.init();
for (int i = 1; i <= m; ++i) {
int u = G[i].u, v = G[i].v;
S[u].insert(v);
S[v].insert(u);
}
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs(i);
}
}
ll ans = 0;
for (int i = 1; i <= m; ++i) {
int u = G[i].u, v = G[i].v, d = G[i].d;
if (merge(u, v)) {
ans += d;
}
}
printf("%lld\n", ans);
}
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%lld%lld%lld", &G[i].u, &G[i].v, &G[i].d);
}
sort(G + 1, G + m + 1, [&](E a, E b) {
return a.d < b.d;
});
if (m >= n * (n - 1) / 2 - n + 1) {
Sub1::solve();
} else {
Sub2::solve();
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}