题目大意：这个题意有些蛋疼，看了很大会才明白什么意思，有N个插座，这些插座都是有类型的只能给这种类型的电器充电，下面接着给了M种电器，和电器的插头类型，还有K种转换器，可以把一种类型转换成另一种，转换器也是可以串联使用的。
输入说明：
首先输入的是一个N，下面有N种插座，每种插座都有一个字符串代表，接着输入一个M，表示有M个电器需要充电，输入的每行有一个电器和它需要的插座类型，然后输入一个K，下面有K个转换器。
分析：这个英文写的这么长确实比较难理解，不过看懂题意后也是比较容易了，可以让电器给可以匹配的插座或者转换器连接，然后让转换器的给别的转换器或者插座连接，虚拟一个源点和所有的手机连接，在虚拟一个汇点让所有的插座与它相连,建图估计有些麻烦.
注意：转换器是无限提供的.......
*********************************************************************************************************************
*********************************************************************************************************************
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; const int MAXN = ;
const int oo = 1e9+; int G[MAXN][MAXN], layer[MAXN];
char s[MAXN][]; bool canLine(char s1[], char s2[])///判断转接口是否相同
{
if(strcmp(s1, s2) == )
return true;
return false;
}
bool bfs(int start, int End)
{
bool used[MAXN] = {};
queue<int> Q; Q.push(start);
memset(layer, -, sizeof(layer));
layer[start] = , used[start] = true; while(Q.size())
{
int u = Q.front();Q.pop(); if(u == End)return true; for(int i=; i<=End; i++)
{
if(G[u][i] && used[i] == false)
{
used[i] = true;
layer[i] = layer[u] + ;
Q.push(i);
}
}
} return false;
}
int dfs(int u, int MaxFlow, int End)
{
if(u == End)return MaxFlow; int uFlow = ; for(int i=; i<=End; i++)
{
if(G[u][i] && layer[i] == layer[u]+)
{
int flow = min(MaxFlow-uFlow, G[u][i]);
flow = dfs(i, flow, End); G[u][i] -= flow;
G[i][u] += flow; uFlow += flow; if(uFlow == MaxFlow)
break;
}
} return uFlow;
}
int dinic(int start, int End)
{
int MaxFlow = ; while( bfs(start, End) == true )
MaxFlow += dfs(start, oo, End); return MaxFlow;
} int main()
{
int N, M, K; while(scanf("%d", &N) != EOF)
{
int i, j; memset(G, , sizeof(G)); for(i=; i<=N; i++)///插头从1~N
scanf("%s", s[i]); scanf("%d", &M);
for(i=; i<=M; i++)///手机从N~N+M,忽略手机名字
scanf("%*s%s", s[i+N]); scanf("%d", &K);
///Ki是转换头进入的开始点，Kj是转换头出去的开始点，start是源点,End是汇点
int Ki = N+M, Kj = Ki+K, start = Kj+K+, End = start+;
for(i=; i<=K; i++)///转换器的进入从N+M~N+M+K，转换器的出从N+M+K~N+M+2*K
{///把入和出连接
scanf("%s%s", s[Ki+i], s[Kj+i]);
G[Ki+i][Kj+i] = oo;///转换器无限提供
} for(i=; i<=M; i++)
{///建立手机和转换器，插座的关系
for(j=; j<=N; j++)
{///匹配一下手机和插座是否直接可以相连
if( canLine(s[i+N], s[j]) == true)
G[i+N][j] = true;
}
for(j=; j<=K; j++)
{///匹配一下手机和转换器入是否可以相连
if( canLine(s[i+N], s[Ki+j]) == true)
G[i+N][Ki+j] = true;
}
} for(i=; i<=K; i++)
{///建立转换器与转换器或者插座的关系
for(j=; j<=K; j++)
{///匹配转换器出与转换器入,转换器无限提供,直接最大值
if(i!=j && canLine(s[Kj+i], s[Ki+j]) == true)
G[Kj+i][Ki+j] = oo;
}
for(j=; j<=N; j++)
{///匹配转换器出和插座的关系
if(canLine(s[Kj+i], s[j]) == true)
G[Kj+i][j] = true;
}
} for(i=; i<=M; i++)
{///源点与手机的关系
G[start][N+i] = true;
}
for(i=; i<=N; i++)
{///插座与汇点的关系
G[i][End] = true;
} printf("%d\n", M-dinic(start, End));
} return ;
}