範例程式碼 uva753
//uva753
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#define MAXN 500
using namespace std;
typedef map<string,int> MSI;
typedef map<string,string> MSS;
int t, n, m, k, nCnt;
bool edge[MAXN][MAXN];
MSI socket;
MSS item;
bool vis[MAXN];
int pre[MAXN];
const bool path(int u) {
int i;
for(i = 1; i <= n; ++i) {
if(edge[u][i] && !vis[i]) {
vis[i] = true;
if(!pre[i] || path(pre[i])) {
pre[i] = u;
return true;
}
}
}
return false;
}
const int maxMatch(void) {
int ret = 0;
memset(pre, 0, sizeof(pre));
for(MSS::iterator it = item.begin(); it != item.end(); ++it) {
memset(vis, false, sizeof(vis));
if(path(socket[(*it).second])) ++ret;
}
return ret;
}
int main(void) {
int i, j, x, y;
string tmps1, tmps2;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
item.clear(); socket.clear();
memset(edge, false, sizeof(edge));
for(i = 1; i <= n; ++i)
cin >> tmps1; socket[tmps1] = i;
scanf("%d", &m);
nCnt = n;
for(i = 1; i <= m; ++i) {
cin >> tmps1 >> tmps2;
item[tmps1] = tmps2;
if(!socket[tmps2]) socket[tmps2] = ++nCnt;
}
scanf("%d", &k);
for(i = 1; i <= k; ++i) {
cin >> tmps1 >> tmps2;
if(!socket[tmps1]) socket[tmps1] = ++nCnt;
if(!socket[tmps2]) socket[tmps2] = ++nCnt;
x = socket[tmps1]; y = socket[tmps2];
edge[x][y] = true;
}
for(i = 1; i <= nCnt; ++i)
edge[i][i] = true;
for(i = 1; i <= nCnt; ++i)
for(x = 1; x <= nCnt; ++x)
for(y = 1; y <= nCnt; ++y)
edge[x][y] |= (edge[x][i]&edge[i][y]);
printf("%d\n", m-maxMatch());
if(t) putchar('\n');
}
return 0;
}