题目链接
不需要将所有边都建立出来，根据\(Kruskal\)最小生成树的贪心策略,相同权值的边不需要形成团，形成一个链就行，对结果没有影响。
时间复杂度\(O(mlogm)[m=\sum_{i=1}^{n} k_{i}]\)。
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
//#define int long long
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int base = 131;
const int inf = INT_MAX;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
vector<int> p(N);
int Find(int x) {
return x == p[x] ? x : p[x] = Find(p[x]);
}
void solve() {
int n, m;
cin >> n >> m;
vector<array<int, 3> > edge;
for (int i = 0; i < m; i++) {
int k, c;
cin >> k >> c;
vector<int> a(k);
for (int j = 0; j < k; j++) {
cin >> a[j];
}
for (int j = 0; j < k - 1; j++) {
edge.push_back({a[j], a[j + 1], c});
}
}
sort(edge.begin(), edge.end(), [](array<int, 3> fi, array<int, 3> se){
return fi[2] < se[2];
});
for (int i = 1; i <= n; i++) {
p[i] = i;
}
ll ans = 0;
int cnt = 0;
for (auto [x, y, c] : edge) {
int fx = Find(x), fy = Find(y);
if (fx != fy) {
p[fx] = fy;
ans += c;
cnt++;
}
}
cout << (cnt == n - 1 ? ans : -1) << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
//cin >> T;
while (T--) {
solve();
}
return 0;
}