at E题求助
  • 板块灌水区
  • 楼主C2026zyl
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/4 21:59
  • 上次更新2024/5/5 09:27:18
查看原帖
at E题求助
1100383
C2026zyl楼主2024/5/4 21:59

此代码本地明明过了样例,交上去却 Wa

#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll, ll>
using namespace std;
const int N = 4e5 + 10;
ll fa[N], siz[N];
map <pii, bool> vis;
struct node {
	ll c;
	vector <ll> a;
	bool operator < (const node & oth) const {
		return c < oth.c;
	}
} s[N];
inline ll find(ll u) {
	if (u == fa[u]) return u;
	return fa[u] = find(fa[u]);
}
inline void merge(ll u, ll v) {
	ll k1 = find(u), k2 = find(v);
	if (k1 == k2) return ;
	if (siz[k1] < siz[k2]) swap(k1, k2);
	fa[k2] = k1;
	siz[k1] += siz[k2];
}
int main() {
	ll n, m; scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1;
	for (int i = 1; i <= m; ++i) {
		ll k, c; scanf("%lld%lld", &k, &c);
		s[i].c = c;
		for (int j = 1, x; j <= k; ++j)
			scanf("%lld", &x), s[i].a.push_back(x);
	}
	stable_sort(s + 1, s + m + 1);
	ll ans = 0, cnt = 0;
	for (int i = 1; i <= m; ++i) {
		for (int j = 0; j < s[i].a.size() - 1; ++j) {
			ll u = s[i].a[j], v = s[i].a[j + 1], w = s[i].c;
			if (find(u) != find(v)) {
				ans += w;
				merge(u, v);
				cnt += 1;
			}
		}
	}
	if (cnt != n - 1) {
		printf("-1");
	} else {
		printf("%lld", ans);
	}
	return 0;
}
2024/5/4 21:59
加载中...