题意：给定n个插座，m个插头，k个转换器（x,y），转换器可以让插头x转成插头y。问最少有多少个插头被剩下。
题解：
最大流或者二分图匹配。然而我不知道怎么打二分图匹配。。
打了最大流。这题字符串比较坑爹，我就先把所有字符串编号（去重），然后给每个点编两个号，一个代表它作为插头的编号，一个代表它作为插座的编号。
最坑的是uvaWA了好久最后发现结尾要有一个回车。。。。。
还有数据范围也是个坑点，点起码要开500。
代码如下：（poj上是单组数据，uva和hdu都是多组）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std; const int N=,L=,INF=(int)1e9;
char s[N][L],c1[L],c2[L];
int ss[N],sc[N],lc[N],rc[N],dis[N],first[N],len,n,m,k,l,num;
struct node{
int x,y,d,next;
}a[];
queue<int> q; int minn(int x,int y){return x<y ? x:y;} void ins(int x,int y,int d)
{
a[++len].x=x;a[len].y=y;a[len].d=d;
a[len].next=first[x];first[x]=len;
a[++len].y=x;a[len].x=y;a[len].d=;
a[len].next=first[y];first[y]=len;
} bool bfs(int st,int ed)
{
while(!q.empty()) q.pop();
memset(dis,-,sizeof(dis));
q.push(st);dis[st]=;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=first[x];i!=-;i=a[i].next)
{
int y=a[i].y;
if(dis[y]==- && a[i].d)
{
dis[y]=dis[x]+;
q.push(y);
}
}
}
return (dis[ed]!=-);
} int dfs(int x,int ed,int flow)
{
if(x==ed) return flow;
int r=;
for(int i=first[x];i!=-;i=a[i].next)
{
int y=a[i].y;
if(dis[y]==dis[x]+ && a[i].d)
{
int p=minn(flow-r,a[i].d);
p=dfs(y,ed,p);
r+=p;
a[i].d-=p;
a[i^].d+=p;
}
}
if(r==) dis[x]=-;
return r;
} int dinic(int st,int ed)
{
int ans=;
while(bfs(st,ed))
ans+=dfs(st,ed,INF);
return ans;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int st,ed;
scanf("%d",&n);
l=;len=-;
memset(first,-,sizeof(first));
memset(sc,,sizeof(sc));
memset(ss,,sizeof(ss));
for(int i=;i<=n;i++)
{
scanf("%s",s[++l]);
bool bk=;
for(int j=;j<l;j++)
{
if(strcmp(s[l],s[j])==)
{
l--,ss[j]++;
bk=;break;
}
}
if(!bk) ss[l]++;
}
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%s",s[++l]);
scanf("%s",s[l]);
bool bk=;
for(int j=;j<l;j++)
{
if(strcmp(s[j],s[l])==)
{
l--,sc[j]++;
bk=;break;
}
}
if(!bk) sc[l]++;
} st=;num=;
for(int i=;i<=l;i++)
{
rc[i]=++num;
lc[i]=++num;
}
scanf("%d",&k);
for(int i=;i<=k;i++)
{
scanf("%s%s",c1,c2);
int t1=,t2=;
for(int j=;j<=l;j++)
{
if(strcmp(c1,s[j])==) t1=j;
if(strcmp(c2,s[j])==) t2=j;
if(t1 && t2) break;
}
if(!t1) t1=++l,strcpy(s[l],c1),lc[l]=++num,rc[l]=++num;
if(!t2) t2=++l,strcpy(s[l],c2),lc[l]=++num,rc[l]=++num;
ins(lc[t1],lc[t2],INF);
}
ed=num+;
for(int i=;i<=l;i++)
{
if(ss[i]) ins(rc[i],ed,ss[i]);
if(sc[i]) ins(st,lc[i],sc[i]);
ins(lc[i],rc[i],INF);
}
printf("%d",m-dinic(st,ed));
if(T) printf("\n\n");
else printf("\n");
}
return ;
}