g.cpp

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

struct Graph {
	int n, source, sink;
	vector<vector<int>> c;

	void Initialize(int _n) {
		n = _n;
		c = vector<vector<int>>(n, vector<int>(n, 0));
	}

	int FindMaxFlow() {
		vector<int> p;
		vector<int> visited(n, 0);
		int total_flow = 0;
		while (FindPath(source, p, visited)) {
			int delta = c[p[0]][p[1]];
			for (int i = 0; i+1 < p.size(); i++)
				delta = min(delta, c[p[i]][p[i+1]]);
			for (int i = 0; i+1 < p.size(); i++) {
				c[p[i]][p[i+1]] -= delta;
				c[p[i+1]][p[i]] += delta;
			}
			total_flow += delta;
			visited = vector<int>(n, 0);
			p.clear();
		}
		return total_flow;
	}

	// Use DFS find a path, returns true if there exists such a path.
	bool FindPath(int x, vector<int>& p, vector<int>& visited) {
		p.push_back(x);
		visited[x] = 1;
		if (x == sink) {
			return true;
		}
		for (int y = 0; y < n; y++)
			if (c[x][y] > 0 && visited[y] == 0 && FindPath(y, p, visited))
				return true;
		p.pop_back();
		return false;
	}
};

map<string, int> names;
int ReadState() {
	string s;
	cin >> s;
	if (names.find(s) == names.end()) {
		int t = names.size();
		names[s] = t;
	}
	return names[s];
}

int main(void) {
	Graph g;
	int s, r, f, t;
	cin >> s >> r >> f >> t;
	g.Initialize(2+s+t*2);
	g.source = 0;
	g.sink = 1;
	vector<int> supplier, factory, company[1005];
	for(int i=0;i<r;i++) supplier.push_back(ReadState());
	for(int i=0;i<f;i++) factory.push_back(ReadState());
	for(int i=0;i<t;i++) {
		int n;
		cin >> n;
		for(int j=0;j<n;j++) {
			int x = ReadState();
			company[x].push_back(i);
		}
	}
	for(int i=0;i<t;i++) g.c[i+2+s][i+t+2+s] = 1;
	for(int i=0;i<s;i++)
		for(auto j : company[i])
			for(auto k : company[i])
				if (j!=k) { g.c[j+t+2+s][k+2+s] = 1; }
	for(auto j : supplier) g.c[0][2+j] = 1;
	for(auto j : factory) g.c[2+j][1] = 1;
	for(auto j : supplier)
		for(auto k : company[j])
			g.c[2+j][2+s+k] = 1;
	for(auto j : factory)
		for(auto k : company[j])
			g.c[2+s+k+t][2+j] = 1;
	
	int ans = g.FindMaxFlow();
	cout << ans << endl;
	return 0;
}