网络流之最大流
网络流一般可以解决形如以上的类似匹配的问题，将复杂，抽象的问题转化成图，在图上跑bfs，dfs，从而简化问题难度。
如此题，有N个插头，M个插座，部分插头可以转化为其他插头，插座与一个插头适配，问最小没有被插的插座的数量，我们可以设一个源点连向插头，插头连向插座，再将插座连想汇点跑最大流即可出答案。
#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const ll inf=1e18,N =300007, M = 300007;
struct node {
ll to, next;
ll w;
}edge[M];
ll tot, head[N];
void addedge(ll u, ll v, ll w) {
edge[++tot].to = v; edge[tot].w = w; edge[tot].next = head[u]; head[u] = tot;
edge[++tot].to = u; edge[tot].w = 0; edge[tot].next = head[v]; head[v] = tot;
}
ll maxflow;
ll n,m,s,t,k,cnt;
ll deep[N]; //层级数，其实应该是level
ll now[M]; //当前弧优化
queue <ll> q;
bool bfs() {
for(int i = 1;i <= t; i++) deep[i] = inf;
while(!q.empty()) q.pop();
q.push(s); deep[s] = 0; now[s] = head[s];
while(!q.empty()) {
ll u = q.front(); q.pop();
for(int i = head[u]; i; i = edge[i].next) {
ll v = edge[i].to;
if(edge[i].w && deep[v] == inf) {
q.push(v);
now[v] = head[v];
deep[v] = deep[u] + 1;
if(v == t) return 1;
}
}
}
return 0;
}
//flow是整条增广路对最大流的贡献，rest是当前最小剩余容量，用rest去更新flow
ll dfs(ll u, ll flow) {
if(u == t) return flow;
ll ans = 0;
for(int i = now[u];i && flow; i = edge[i].next) {
now[u] = i; //当前弧优化（避免重复遍历从x出发的不可拓展的边）
ll v = edge[i].to;
if(edge[i].w && deep[v] == deep[u]+1) { //必须是下一层并且剩余容量大于0
ll k = dfs(v, min(flow, edge[i].w)); //取最小
if(!k) deep[v] = inf; //剪枝，去掉增广完毕的点
edge[i].w -= k; //回溯时更新
edge[i^1].w += k; //成对变换
ans += k;
flow -= k;
}
}
return ans;
}
void dinic() {
while(bfs())
maxflow += dfs(s, inf);
}
string s1,s2;
map<string,ll>ma;
int main(){
scanf("%lld",&n);
tot=1;
s=1000,t=1001;
for(int i=1;i<=n;i++){
cin>>s1;
if(ma[s1]==0){
ma[s1]=++cnt;
addedge(ma[s1],t,1);
}
}
scanf("%lld",&m);
for(int i=1;i<=m;i++){
cin>>s1>>s2;
addedge(s,++cnt,1);
if(ma[s2]==0){
ma[s2]=++cnt;
addedge(cnt-1,ma[s2],1);
}
else{
addedge(cnt,ma[s2],1);
}
}
scanf("%lld",&k);
for(int i=1;i<=k;i++){
cin>>s1>>s2;
if(ma[s1]==0){
ma[s1]=++cnt;
}
if(ma[s2]==0){
ma[s2]=++cnt;
}
addedge(ma[s1],ma[s2],inf);
}
dinic();
printf("%lld
",m-maxflow);
}