lessons/参考实现/06-最小与最大生成树/CodeForces-1408E.cpp

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, size;
    explicit DSU(int n) : parent(n), size(n, 1) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a; size[a] += size[b];
        return true;
    }
};

struct Edge { int u, v; long long weight; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int sets, values;
    cin >> sets >> values;
    vector<long long> a(sets), b(values);
    for (long long &x : a) cin >> x;
    for (long long &x : b) cin >> x;
    vector<Edge> edges;
    long long total = 0;
    for (int i = 0; i < sets; ++i) {
        int size;
        cin >> size;
        while (size--) {
            int value;
            cin >> value;
            --value;
            long long weight = a[i] + b[value];
            edges.push_back({i, sets + value, weight});
            total += weight;
        }
    }
    sort(edges.begin(), edges.end(), [](const Edge &x, const Edge &y) {
        return x.weight > y.weight;
    });
    DSU dsu(sets + values);
    long long kept = 0;
    for (const Edge &edge : edges) {
        if (dsu.unite(edge.u, edge.v)) kept += edge.weight;
    }
    cout << total - kept << '\n';
    return 0;
}