题意：给定n个插座，m个插头，k个转换器（x,y），转换器可以让插头x转成插头y。问最少有多少个插头被剩下。
题解：
最大流或者二分图匹配。然而我不知道怎么打二分图匹配。。
打了最大流。这题字符串比较坑爹，我就先把所有字符串编号（去重），然后给每个点编两个号，一个代表它作为插头的编号，一个代表它作为插座的编号。
最坑的是uvaWA了好久最后发现结尾要有一个回车。。。。。
还有数据范围也是个坑点，点起码要开500。
代码如下：（poj上是单组数据，uva和hdu都是多组）
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<queue> 6 using namespace std; 7 8 const int N=1010,L=110,INF=(int)1e9; 9 char s[N][L],c1[L],c2[L]; 10 int ss[N],sc[N],lc[N],rc[N],dis[N],first[N],len,n,m,k,l,num; 11 struct node{ 12 int x,y,d,next; 13 }a[100010]; 14 queue<int> q; 15 16 int minn(int x,int y){return x<y ? x:y;} 17 18 void ins(int x,int y,int d) 19 { 20 a[++len].x=x;a[len].y=y;a[len].d=d; 21 a[len].next=first[x];first[x]=len; 22 a[++len].y=x;a[len].x=y;a[len].d=0; 23 a[len].next=first[y];first[y]=len; 24 } 25 26 bool bfs(int st,int ed) 27 { 28 while(!q.empty()) q.pop(); 29 memset(dis,-1,sizeof(dis)); 30 q.push(st);dis[st]=0; 31 while(!q.empty()) 32 { 33 int x=q.front();q.pop(); 34 for(int i=first[x];i!=-1;i=a[i].next) 35 { 36 int y=a[i].y; 37 if(dis[y]==-1 && a[i].d) 38 { 39 dis[y]=dis[x]+1; 40 q.push(y); 41 } 42 } 43 } 44 return (dis[ed]!=-1); 45 } 46 47 int dfs(int x,int ed,int flow) 48 { 49 if(x==ed) return flow; 50 int r=0; 51 for(int i=first[x];i!=-1;i=a[i].next) 52 { 53 int y=a[i].y; 54 if(dis[y]==dis[x]+1 && a[i].d) 55 { 56 int p=minn(flow-r,a[i].d); 57 p=dfs(y,ed,p); 58 r+=p; 59 a[i].d-=p; 60 a[i^1].d+=p; 61 } 62 } 63 if(r==0) dis[x]=-1; 64 return r; 65 } 66 67 int dinic(int st,int ed) 68 { 69 int ans=0; 70 while(bfs(st,ed)) 71 ans+=dfs(st,ed,INF); 72 return ans; 73 } 74 75 int main() 76 { 77 int T; 78 scanf("%d",&T); 79 while(T--) 80 { 81 int st,ed; 82 scanf("%d",&n); 83 l=0;len=-1; 84 memset(first,-1,sizeof(first)); 85 memset(sc,0,sizeof(sc)); 86 memset(ss,0,sizeof(ss)); 87 for(int i=1;i<=n;i++) 88 { 89 scanf("%s",s[++l]); 90 bool bk=0; 91 for(int j=1;j<l;j++) 92 { 93 if(strcmp(s[l],s[j])==0) 94 { 95 l--,ss[j]++; 96 bk=1;break; 97 } 98 } 99 if(!bk) ss[l]++; 100 } 101 scanf("%d",&m); 102 for(int i=1;i<=m;i++) 103 { 104 scanf("%s",s[++l]); 105 scanf("%s",s[l]); 106 bool bk=0; 107 for(int j=1;j<l;j++) 108 { 109 if(strcmp(s[j],s[l])==0) 110 { 111 l--,sc[j]++; 112 bk=1;break; 113 } 114 } 115 if(!bk) sc[l]++; 116 } 117 118 st=0;num=0; 119 for(int i=1;i<=l;i++) 120 { 121 rc[i]=++num; 122 lc[i]=++num; 123 } 124 scanf("%d",&k); 125 for(int i=1;i<=k;i++) 126 { 127 scanf("%s%s",c1,c2); 128 int t1=0,t2=0; 129 for(int j=1;j<=l;j++) 130 { 131 if(strcmp(c1,s[j])==0) t1=j; 132 if(strcmp(c2,s[j])==0) t2=j; 133 if(t1 && t2) break; 134 } 135 if(!t1) t1=++l,strcpy(s[l],c1),lc[l]=++num,rc[l]=++num; 136 if(!t2) t2=++l,strcpy(s[l],c2),lc[l]=++num,rc[l]=++num; 137 ins(lc[t1],lc[t2],INF); 138 } 139 ed=num+1; 140 for(int i=1;i<=l;i++) 141 { 142 if(ss[i]) ins(rc[i],ed,ss[i]); 143 if(sc[i]) ins(st,lc[i],sc[i]); 144 ins(lc[i],rc[i],INF); 145 } 146 printf("%d",m-dinic(st,ed)); 147 if(T) printf("\n\n"); 148 else printf("\n"); 149 } 150 return 0; 151 }