UVA 753 - A Plug for UNIX(网络流）(二)
3f3f3f const int N = 1005; int T, n, m, k, sum, g[N][N], f[N][N], p[N], a[N]; char str[30], str1[30], name[N][30]; queue
q; int find(char *str) { for (int i = 0; i < sum; i ++) if (strcmp(str, name[i]) == 0) return i + 1; strcpy(name[sum ++], str); return sum; } void init() { sum = 0; memset(g, 0, sizeof(g)); scanf("%d", &n); for (int i = 0; i < n; i ++) { scanf("%s", str); g[0][find(str)] ++; } scanf("%d", &m); for (int i = 0; i < m; i ++) { scanf("%s%s", str1, str); p[i] = find(str); } scanf("%d", &k); for (int i = 0; i < k; i ++) { scanf("%s%s", str, str1); int u = find(str); int v = find(str1); g[v][u] = INF; } for (int i = 0; i < m; i ++) { g[p[i]][sum + 1] ++; } } int solve() { init(); memset(f, 0, sizeof(f)); memset(p, 0, sizeof(p)); int s = 0, t = sum + 1, ans = 0; while (1) { memset(a, 0, sizeof(a)); a[s] = INF; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 1; v <= t; v ++) { if (!a[v] && g[u][v] > f[u][v]) { a[v] = min(a[u], g[u][v] - f[u][v]); p[v] = u; q.push(v); } } } if (a[t] == 0) break; for (int u = t; u != s; u = p[u]) { f[p[u]][u] += a[t]; f[u][p[u]] -= a[t]; } ans += a[t]; } return m - ans; } int main() { scanf("%d", &T); while (T --) { printf("%d\n", solve()); if (T) printf("\n"); } return 0; }