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