只是单纯的为了存模板 = =!
#include<map>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 1111111111;
const int maxn = 444;
const int maxd = 111111;
int nn,mm,kk,cnt;
int floyd[maxn][maxn];
int array[maxn]; //设备插头数组
int array2[maxn]; //插座数组
map<string,int>idm; //插座编码
vector<string>idv; //插座数组
//-------------------------网络流模板---------------------------
struct Edge{
int from,to,cap,flow;//容量 流量
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){};
};
struct EdmondsKarp{
int n,m;
vector<Edge>edges;
vector<int>G[maxn]; //结点i的第j条边是编号多少
int a[maxn]; //起点到i的可改进量
int p[maxn];
void init(int n){
for(int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from,0,0)); //反向弧
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
int Maxflow(int s,int t){
int flow = 0;
while(true){
memset(a,0,sizeof(a));
queue<int>Q;
Q.push(s); //加入起点
a[s] = INF;
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(int i = 0; i < G[x].size(); i++){
Edge &e = edges[G[x][i]];
if(!a[e.to] && e.cap > e.flow){
p[e.to] = G[x][i]; //
a[e.to] = min(a[x],e.cap - e.flow);
Q.push(e.to);
}
}
if(a[t]) break;
}
if(!a[t]) break;
for(int u = t; u != s; u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
}
flow += a[t];
}
return flow;
}
}edm;
//------------------------------------------------------------
void debug(){
for(int i = 0; i < idv.size(); i++)
cout << idv[i] << endl;
for(int i = 1; i < cnt; i++){
for(int j = 1; j < cnt; j++)
printf("%d ",floyd[i][j]);
puts("");
}
for(int i = 0; i < nn; i++)
printf("%d ",array2[i]);
puts("");
for(int i = 0; i < mm; i++)
printf("%d ",array[i]);
puts("");
}
void Floyd(){ //利用F loyd判断重复
for(int i = 1; i < cnt; i++) floyd[i][i] = 1;
for(int k = 1; k < cnt; k++)
for(int i = 1; i < cnt; i++)
for(int j = 1; j < cnt; j++){
if(floyd[i][k] && floyd[k][j])
floyd[i][j] = 1;
}
}
void solve(){
for(int i = 0; i < mm; i++){ //插座
for(int j = 0; j < nn; j++){ //插头
int e1 = array[i],e2 = array2[j];
if(floyd[e1][e2]){
//printf("%d %d\n",i + 1,mm + 1 + j);
edm.AddEdge(i + 1,mm + 1 + j,INF);
}
}
}
for(int i = 0; i < mm; i++){
//printf("0 %d\n",i + 1);
edm.AddEdge(0,i + 1,1);
}
for(int i = 0; i < nn; i++){
//printf("%d %d\n",mm + 1 + i,nn + mm + 1);
edm.AddEdge(mm + 1 + i,nn + mm + 1,1);
}
int ff = edm.Maxflow(0,nn + mm + 1);
printf("%d\n",mm - ff);
}
int main(){
int T;
char str[30],str2[30];
scanf("%d",&T);
while(T--){
memset(floyd,0,sizeof(floyd)); //init
edm.init(422);
cnt = 1;
idm.clear();
idv.clear();
scanf("%d",&nn); //插座
for(int i = 0; i < nn; i++){
scanf("%s",str);
string sstr(str);
if(!idm[sstr]){
idv.push_back(str);
idm[sstr] = cnt++;
}
array2[i] = idm[sstr];
}
scanf("%d",&mm); //插头
for(int i = 0; i < mm; i++){
scanf("%*s%s",str);
string sstr(str);
if(!idm[sstr]){
idv.push_back(str);
idm[sstr] = cnt++;
}
array[i] = idm[sstr];
}
scanf("%d",&kk);
for(int i = 0; i < kk; i++){
scanf("%s%s",str,str2);
string sstr1(str),sstr2(str2);
if(!idm[sstr1]){
idv.push_back(sstr1);
idm[sstr1] = cnt++;
}
if(!idm[sstr2]){
idv.push_back(sstr2);
idm[sstr2] = cnt++;
}
int e1 = idm[sstr1],e2 = idm[sstr2];
floyd[e1][e2] = 1;
//printf("%d %d\n",e1,e2);
}
Floyd();
//debug();
solve();
if(T) puts("");
}
return 0;
}
原文：http://blog.csdn.net/u013451221/article/details/44564301