#include #include #include #include using namespace std; typedef long long ll; template struct stable_matching { public: struct Edge { int a, b; int preference_a, preference_b; // The smaller the value, the higher the priority. bool is_matched; T cost; int id; bool operator<(const Edge &e) const { return preference_a < e.preference_a; } }; stable_matching() {} stable_matching(int p, int q) : p(p), q(q), m(0) { g.resize(p); } void add_directed_edge(int a, int b, int preference_a, int preference_b, T cost = 1) { assert(0 <= a && a < p); assert(0 <= b && b < q); epos.push_back(std::pair(a, (int)g[a].size())); g[a].push_back((Edge){a, b, preference_a, preference_b, false, cost, m++}); } void get_stable_matching() { for (int a = 0; a < p; a++) { if (!std::is_sorted(g[a].begin(), g[a].end())) { std::sort(g[a].begin(), g[a].end()); } } std::vector> match(q, std::pair(-1, -1)); std::vector nx(p, 0); std::queue que; for (int a = 0; a < p; a++) { que.push(a); } while (que.size()) { int a = que.front(); que.pop(); for (int &i = nx[a]; i < (int)g[a].size(); i++) { int b = g[a][i].b; int x = match[b].first; int j = match[b].second; if (x >= 0 && g[a][i].preference_b < g[x][j].preference_b) { g[x][j].is_matched = false; nx[x]++; que.push(x); x = -1; } if (x == -1) { g[a][i].is_matched = true; match[b] = std::pair(a, i); break; } } } } std::vector get_matching_edges() { std::vector res; for (int i = 0; i < m; i++) { Edge e = g[epos[i].first][epos[i].second]; if (e.is_matched) { res.push_back(e); } } return res; } Edge &get_edge(int id) { assert(id < m); return g[epos[id].first][epos[id].second]; } int get_size() { return p + q; } int get_left_size() { return p; } int get_right_size() { return q; } int get_edge_size() { return m; } private: int p, q, m; std::vector> g; std::vector> epos; }; void solve() { int n, x, y; cin >> n >> x >> y; int p[200005], d[200005]; for (int u = 0; u < n; u++) { p[u] = -1; } int k[200005]; for (int i = 0; i < x; i++) { cin >> k[i]; for (int j = 0; j <= k[i]; j++) { int u; cin >> u; u--; p[u] = i; d[u] = j; } } stable_matching g(x, y); int m = 0; for (int i = 0; i < y; i++) { int l; cin >> l; for (int j = 0; j <= l; j++) { int v; cin >> v; v--; if (p[v] >= 0) { g.add_directed_edge(p[v], i, d[v], -j); } } } g.get_stable_matching(); int ans = 0; for (int i = 0; i < x; i++) { ans += k[i]; } auto M = g.get_matching_edges(); for (auto &e : M) { ans -= k[e.a] - e.preference_a; } cout << ans << endl; } int main() { solve(); }