https://www.luogu.com.cn/problem/AT_abc270_f

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, tot = 0, last_tot = 0, x[20000005], y[20000005], fa[20000005];
struct no {
	int a, b, w;
} ed[20000005];
bool cmp (no a, no b) {
	return a.w < b.w;
}
void init () {
	for (int i = 1; i <= n + 2; i++)fa[i] = i;
}
int find (int x) {
	if (fa[x] == x) return x;
	return fa[x] = find (fa[x]);
}
int kruscal () {
	sort (ed + 1, ed + 1 + tot, cmp);
	init ();
	int res = 0, cnt = 0;
	for (int i = 1; i <= tot; i++) {
		int a = ed[i].a, b = ed[i].b, w = ed[i].w;
		a = find (a), b = find (b);
		if (a != b) {
			fa[a] = b;
			res += w;
			cnt ++;
		}
	}
	if (cnt < n - 1)return LLONG_MAX;
	else return res;
}
int kruscall() {
	sort (ed + 1, ed + 1 + last_tot, cmp);
	init ();
	int res = 0, cnt = 0;
	for (int i = 1; i <= last_tot; i++) {
		int a = ed[i].a, b = ed[i].b, w = ed[i].w;
		a = find (a), b = find (b);
		if (a != b) {
			fa[a] = b;
			res += w;
			cnt ++;
		}
	}
	if (cnt < n - 1)return LLONG_MAX;
	else return res;
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> y[i];
	}
	for (int x, y, v, i = 1; i <= m; i++) {
		cin >> x >> y >> v;
		ed[++tot] = {x, y, v};
		ed[++tot] = {y, x, v};
	}
	int ans1 = kruscal(), last_tot = tot;
	for (int i = 1; i <= n; i++) {
		ed[++tot] = {i, n + 1, x[i]};
		ed[++tot] = {n + 1, i, x[i]};
	}
	int ans2 = kruscal();
	for (int i = 1; i <= n; i++) {
		ed[++tot] = {i, n + 2, y[i]};
		ed[++tot] = {n + 2, i, y[i]};
	}
	int ans3 = kruscal();
	for (int i = 1; i <= n; i++) {
		ed[++last_tot] = {i, n + 1, y[i]};
		ed[++last_tot] = {n + 1, i, y[i]};
	}
	int ans4 = kruscall();
	cout << min(min(ans1, ans2), min(ans3, ans4));
	return 0;
}