看完题以后就觉得是个最大流了。然后脑子不太清醒，想了一会儿才发现建图好简单啊，不过中间理解错题意了，题目中说有K种适配器，也就是说每种适配器的数量是无限个的，而我理解成了K个适配器了。。。 然后就WA了几次。。。
建图： 加一个超级源点， 超级汇点。
源点与每个电器相连，容量为1，每个电器与其相应的插座相连，容量为1，插座之间能转化的就连一条无限容量的边，最后每个插座跟汇点相连，容量为这种类型的插座的个数。
需要注意的是，最后图中的节点数可能会达到400之多。题目的数据可能会给出一些看起来毫无用处的适配器，比如把一个数量为0的插座类型转化为另一种数量为0的插座类型。 这个也是要计算在内的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <map>
#include <algorithm>
#define MAXN 505
#define MAXM 500005
#define INF 1111111111
using namespace std;
struct node
{int ver; // vertexint cap; // capacityint flow; // current flow in this arcint next, rev;
}edge[MAXM];
int dist[MAXN], numbs[MAXN], src, des, n;
int head[MAXN], e;
void add(int x, int y, int c)
{ //e记录边的总数//printf("%d %d %d\n", x, y, c);edge[e].ver = y;edge[e].cap = c;edge[e].flow = 0;edge[e].rev = e + 1; //反向边在edge中的下标位置edge[e].next = head[x]; //记录以x为起点的上一条边在edge中的下标位置head[x] = e++; //以x为起点的边的位置//反向边edge[e].ver = x;edge[e].cap = 0; //反向边的初始网络流为0edge[e].flow = 0;edge[e].rev = e - 1;edge[e].next = head[y];head[y] = e++;
}
void rev_BFS()
{int Q[MAXN], qhead = 0, qtail = 0;for(int i = 1; i <= n; ++i){dist[i] = MAXN;numbs[i] = 0;}Q[qtail++] = des;dist[des] = 0;numbs[0] = 1;while(qhead != qtail){int v = Q[qhead++];for(int i = head[v]; i != -1; i = edge[i].next){if(edge[edge[i].rev].cap == 0 || dist[edge[i].ver] < MAXN)continue;dist[edge[i].ver] = dist[v] + 1;++numbs[dist[edge[i].ver]];Q[qtail++] = edge[i].ver;}}
}
void init()
{e = 0;memset(head, -1, sizeof(head));
}
int maxflow()
{int u, totalflow = 0;int Curhead[MAXN], revpath[MAXN];for(int i = 1; i <= n; ++i)Curhead[i] = head[i];u = src;while(dist[src] < n){if(u == des) // find an augmenting path{int augflow = INF;for(int i = src; i != des; i = edge[Curhead[i]].ver)augflow = min(augflow, edge[Curhead[i]].cap);for(int i = src; i != des; i = edge[Curhead[i]].ver){edge[Curhead[i]].cap -= augflow;edge[edge[Curhead[i]].rev].cap += augflow;edge[Curhead[i]].flow += augflow;edge[edge[Curhead[i]].rev].flow -= augflow;}totalflow += augflow;u = src;}int i;for(i = Curhead[u]; i != -1; i = edge[i].next)if(edge[i].cap > 0 && dist[u] == dist[edge[i].ver] + 1)break;if(i != -1) // find an admissible arc, then Advance{Curhead[u] = i;revpath[edge[i].ver] = edge[i].rev;u = edge[i].ver;}else // no admissible arc, then relabel this vertex{if(0 == (--numbs[dist[u]]))break; // GAP cut, Important!Curhead[u] = head[u];int mindist = n;for(int j = head[u]; j != -1; j = edge[j].next)if(edge[j].cap > 0)mindist = min(mindist, dist[edge[j].ver]);dist[u] = mindist + 1;++numbs[dist[u]];if(u != src)u = edge[revpath[u]].ver; // Backtrack}}return totalflow;
}
int num[505];
int main()
{int nt, m, k;string str1, str2;map<string ,int>plug;init();scanf("%d", &nt);int cnt = 0;for(int i = 0; i < nt; i++){cin >> str1;if(plug[str1] == 0) plug[str1] = ++cnt;num[plug[str1]]++;}scanf("%d", &m);int t = cnt;src = 1;for(int i = 0; i < m; i++){cin >> str1 >> str2;if(plug[str2] == 0) plug[str2] = ++cnt;add(2 + i, plug[str2] + m + 1, 1);add(src, 2 + i, 1);}scanf("%d", &k);for(int i = 0; i < k; i++){cin >> str1 >> str2;if(plug[str1] == 0) plug[str1] = ++cnt;if(plug[str2] == 0) plug[str2] = ++cnt;add(plug[str1] + m + 1, plug[str2] + m + 1, INF);}n = 2 + m + cnt;des = n;for(int i = 1; i <= t; i++) add(m + 1 + i, des, num[i]);//printf("ss %d %d\n", src, des);rev_BFS();int ans = m - maxflow();printf("%d\n", ans);return 0;
}