问题
分析
添加两个节点，一个源节点，一个宿节点
解法1:首先用floyd算出所有的转换器之间的连接关系，然后将插头和插座看作点，转换器作为边，容量是INF，连接源点和每个插头，每个插座和宿节点，容量是1，计算最大流量
解法2：不适用Floyd，直接构图，每个出现过的插头或者插座都看作一个节点，将转换器看作边，容量INF，添加源节点，宿节点
解法1：
EK :
//
// Created by Zhao Pengfei on 2020/2/16.
//
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <utility>
#include <map>
#include <string>
#include <queue>
using namespace std;
const int maxn=105,Inf=0x3f3f3f3f;
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[4*maxn];
int a[4*maxn];
int p[4*maxn];
void init(int n){
this->n=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; //到达了t，提前退出
}
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;
}
};
int kase,id,n,m,k,recept[4*maxn],plug[4*maxn],g[4*maxn][4*maxn];
map<string,int> str2int;
vector<string> int2str;
string s1,s2;
int ID(string &s){
if(str2int.count(s)) return str2int[s];
int2str.push_back(s);
return str2int[s]=int2str.size()-1;
}
int main(void){
scanf("%d",&kase);
while(kase--){
memset(g,0,sizeof(g));
str2int.clear();
int2str.clear();
scanf("%d",&n);
for(int i=0;i<n;++i){
cin>>s1;
recept[i]=ID(s1);
}
scanf("%d",&m);
for(int i=0;i<m;++i){
cin>>s1>>s2;
plug[i]=ID(s2);
}
scanf("%d",&k);
for(int i=0;i<k;++i){
cin>>s1>>s2;
g[ID(s1)][ID(s2)]=1;
}
int V=int2str.size();
// for(int i=0;i<V;++i) g[i][i]=1;
for(int k=0;k<V;++k){
for(int i=0;i<V;++i){
for(int j=0;j<V;++j){
g[i][j]=g[i][j]||(g[i][k] && g[k][j]);
}
}
}
EdmondsKarp ek;
ek.init(V+2); //添加源点和汇点
//下面要注意插座和插头，不要搞反了
for(int i=0;i<m;++i){
ek.AddEdge(V,plug[i],1); //添加源点->插头
}
for(int i=0;i<n;++i){
ek.AddEdge(recept[i],V+1,1); //添加插座->汇点
}
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(g[plug[i]][recept[j]]){ //添加 插头->插座
ek.AddEdge(plug[i],recept[j],Inf);
}
}
}
int f=ek.MaxFlow(V,V+1);
printf("%d\n",m-f);
if(kase) printf("\n");
}
return 0;
}
Dinic:
//
// Created by Zhao Pengfei on 2020/2/16.
//
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <utility>
#include <map>
#include <string>
#include <queue>
using namespace std;
const int maxn=105,Inf=0x3f3f3f3f;
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 Dinic{
int n,m;
vector<Edge> edges;
vector<int> G[4*maxn];
int d[4*maxn];
void init(int n){
this->n=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);
}
bool BFS(int s,int t){
memset(d,-1,sizeof(d));
queue<int> Q;
d[s]=0;
Q.push(s);
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(d[e.to]<0 && e.cap>e.flow){
d[e.to]=d[x]+1;
Q.push(e.to);
if(e.to==t) return true;
}
}
}
return d[t]>=0;
}
//cur代表现在所在的节点，a代表增加数量
int DFS(int cur,int t,int a){
if(cur==t || a==0) return a;
int flow=0,f;
for(int i=0;i<G[cur].size();++i){
Edge &e=edges[G[cur][i]];
if(d[e.to]==d[cur]+1 && (f=DFS(e.to,t,min(a,e.cap-e.flow)))>0){
e.flow+=f;
edges[G[cur][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0) break;
}
}
return flow;
}
int MaxFlow(int s,int t){
int flow=0;
while(BFS(s,t)){
flow+=DFS(s,t,Inf);
}
return flow;
}
};
int kase,id,n,m,k,recept[maxn],plug[maxn],g[4*maxn][4*maxn];
map<string,int> str2int;
vector<string> int2str;
string s1,s2;
int ID(string &s){
if(str2int.count(s)) return str2int[s];
int2str.push_back(s);
return str2int[s]=int2str.size()-1;
}
int main(void){
scanf("%d",&kase);
while(kase--){
memset(g,0,sizeof(g));
str2int.clear();
int2str.clear();
scanf("%d",&n);
for(int i=0;i<n;++i){
cin>>s1;
recept[i]=ID(s1);
}
scanf("%d",&m);
for(int i=0;i<m;++i){
cin>>s1>>s2;
plug[i]=ID(s2);
}
scanf("%d",&k);
for(int i=0;i<k;++i){
cin>>s1>>s2;
g[ID(s1)][ID(s2)]=1;
}
int V=int2str.size();
// for(int i=0;i<V;++i) g[i][i]=1;
for(int k=0;k<V;++k){
for(int i=0;i<V;++i){
for(int j=0;j<V;++j){
g[i][j]=g[i][j]||(g[i][k] && g[k][j]);
}
}
}
Dinic Din;
Din.init(V+2); //添加源点和汇点
//下面要注意插座和插头，不要搞反了
for(int i=0;i<m;++i){
Din.AddEdge(V,plug[i],1); //添加源点->插头
}
for(int i=0;i<n;++i){
Din.AddEdge(recept[i],V+1,1); //添加插座->汇点
}
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(g[plug[i]][recept[j]]){ //添加 插头->插座
Din.AddEdge(plug[i],recept[j],Inf);
}
}
}
int f=Din.MaxFlow(V,V+1);
printf("%d\n",m-f);
if(kase) printf("\n");
}
return 0;
}
解法2：
//
// Created by Zhao Pengfei on 2020/2/16.
//
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <utility>
#include <map>
#include <string>
#include <queue>
using namespace std;
const int maxn=105,Inf=0x3f3f3f3f;
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[4*maxn];
int a[4*maxn];
int p[4*maxn];
void init(int n){
this->n=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; //到达了t，提前退出
}
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;
}
};
int kase,id,n,m,k,recept[4*maxn],plug[4*maxn],transfer[2][4*maxn];
map<string,int> str2int;
vector<string> int2str;
string s1,s2;
int ID(string &s){
if(str2int.count(s)) return str2int[s];
int2str.push_back(s);
return str2int[s]=int2str.size()-1;
}
int main(void){
scanf("%d",&kase);
while(kase--){
str2int.clear();
int2str.clear();
scanf("%d",&n);
for(int i=0;i<n;++i){
cin>>s1;
recept[i]=ID(s1);
}
scanf("%d",&m);
for(int i=0;i<m;++i){
cin>>s1>>s2;
plug[i]=ID(s2);
}
scanf("%d",&k);
for(int i=0;i<k;++i){
cin>>s1>>s2;
transfer[0][i]=ID(s1);
transfer[1][i]=ID(s2);
}
int V=int2str.size();
EdmondsKarp ek;
ek.init(V+2); //添加源点和汇点
//下面要注意插座和插头，不要搞反了
for(int i=0;i<m;++i){
ek.AddEdge(V,plug[i],1); //添加源点->插头
}
for(int i=0;i<n;++i){
ek.AddEdge(recept[i],V+1,1); //添加插座->汇点
}
for(int i=0;i<k;++i){
//添加 插头->插座
ek.AddEdge(transfer[0][i],transfer[1][i],Inf);
}
int f=ek.MaxFlow(V,V+1);
printf("%d\n",m-f);
if(kase) printf("\n");
}
return 0;
}