在会议开始之前，你收集所有记者想要使用的设备，并尝试设置它们。你注意到有些设备使用没有插座的插头。你想知道这些设备是否来自建造这个房间时并不存在的国家。对于一些插座，有几个设备使用相应的插头。对于其他插座，没有使用相应插头的设备。
为了解决这个问题，你可以去附近的零件供应商店。该商店出售的适配器允许在不同类型的插座上使用一种类型的插头。此外，还允许将适配器插入到其他适配器中。该商店没有为所有可能的插头和插座组合提供适配器，但实际上他们有无限的供应。
输入
输入将包括一种情况。第一行包含一个正整数n (1 <= n <= 100)，表示房间中插座的数量。接下来的n行列出了在房间中找到的容器类型。每个容器类型由最多24个字母数字字符组成的字符串组成。下一行包含一个正整数m (1 <= m <= 100)，表示要插入的设备数量。接下来的m行每一行都列出了一个设备的名称，后面跟着它使用的插头类型(与它需要的插座类型相同)。设备名称是一个最多24个字母数字组成的字符串
字符。没有两个设备会有完全相同的名称。插头类型与设备名称之间用空格分隔。下一行包含一个正整数k (1 <= k <= 100)，表示可用的适配器的不同种类的数量。接下来的k行描述了各种适配器，给出了适配器提供的插座类型，后面是空格，后面是插头类型。
输出
包含单个非负整数的行，它表示不能插入的设备的最小数目。
代码：
1 //题目上面说的是一种电脑有一种类型的插头，电脑要充电就必须找对应的插座。除此之外你还可以找一个转换器去把电脑插头类型转换一下 2 //那就可以定义一个st代表最大流起点，en代表最大流终点。 3 // 4 //st起点就要和每一台电脑相连，然后再让电脑和转换器连接(连接要求就是连接器开头要和电脑插头类型一样) 5 //最后再和插头相连。插头再和终点en相连就可以了。具体看代码吧 6 // 7 #include<stdio.h> 8 #include<string.h> 9 #include<iostream> 10 #include<algorithm> 11 #include<queue> 12 #include<map> 13 using namespace std; 14 const int maxn=1005; 15 const int INF=0x3f3f3f3f; 16 int head[maxn],cnt,st,en,dis[maxn],cur[maxn]; 17 map<string,int>r; 18 struct edge 19 { 20 int v,next,c,flow; 21 } e[maxn]; 22 struct shudui 23 { 24 string q; 25 int qq; 26 } p[maxn]; 27 void add_edge(int x,int y,int z) 28 { 29 e[cnt].v=y; 30 e[cnt].c=z; 31 e[cnt].flow=0; 32 e[cnt].next=head[x]; 33 head[x]=cnt++; 34 } 35 bool bfs() 36 { 37 memset(dis,0,sizeof(dis)); 38 dis[st]=1; 39 queue<int>r; 40 r.push(st); 41 while(!r.empty()) 42 { 43 int x=r.front(); 44 r.pop(); 45 for(int i=head[x]; i!=-1; i=e[i].next) 46 { 47 int v=e[i].v; 48 if(!dis[v] && e[i].c>e[i].flow) 49 { 50 dis[v]=dis[x]+1; 51 r.push(v); 52 } 53 } 54 } 55 return dis[en]; 56 } 57 int dinic(int s,int limit) 58 { 59 if(s==en || !limit) return limit; 60 int ans=0; 61 for(int &i=cur[s]; i!=-1; i=e[i].next) 62 { 63 int v=e[i].v,feed; 64 if(dis[v]!=dis[s]+1) continue; 65 feed=dinic(v,min(limit,e[i].c-e[i].flow)); 66 if(feed) 67 { 68 e[i].flow+=feed; 69 e[i^1].flow-=feed; 70 limit-=feed; 71 ans+=feed; 72 if(limit==0) break; 73 } 74 } 75 if(!ans) dis[s]=-1; 76 return ans; 77 } 78 int main() 79 { 80 int n,m,k,index=1; 81 while(~scanf("%d",&n)) 82 { 83 cnt=0; 84 memset(head,-1,sizeof(head)); 85 index=1; 86 string qq,q; 87 st=0; 88 en=1; 89 for(int i=2; i<=n+1; ++i) 90 { 91 cin>>q; 92 r[q]=++index; 93 add_edge(r[q],en,1); //插头和终点相连 94 add_edge(en,r[q],0); 95 } 96 scanf("%d",&m); 97 index=n+2+2*m; 98 for(int i=n+2; i<=n+1+m; ++i) 99 { 100 cin>>q>>q; 101 p[i-n-1].q=q; 102 p[i-n-1].qq=i+m; 103 add_edge(st,i,INF); //电脑和起点相连 104 add_edge(i,st,0); 105 add_edge(i,i+m,1); //这里也就是对电脑进行拆点了，不拆点的话应该也可以 106 add_edge(i+m,i,0); 107 if(r[q]==0) r[q]=++index; 108 add_edge(i+m,r[q],1); //找到对应插头进行连接 109 add_edge(r[q],i+m,0); 110 111 } 112 scanf("%d",&k); 113 while(k--) 114 { 115 cin>>qq>>q; 116 add_edge(r[qq],r[q],INF); //转换器能使用多次，所以要建一个容量为INF的边 117 add_edge(r[q],r[qq],0); 118 } 119 r.clear(); 120 int ans=0; 121 while(bfs()) 122 { 123 for(int i=0; i<=index; i++) 124 cur[i]=head[i]; 125 ans+=dinic(st,1); //1可以改成无穷大 126 } 127 printf("%d ",m-ans); 128 } 129 130 return 0; 131 }