题意：
给n个插座，m个设备（肯定要插电了），k种转换头可无限次使用（注意是单向的），问有多少设备最终是不能够插上插座的？
分析：
看起来就是设备匹配插座，所以答案不超过m。这个题适合用网络流来解。
假设每种头对应着一个编号（可以用map实现转换string到int），主要在k种转换头的建边，他们之间的转换关系就是编号与编号之间的边，因为可以无限次使用，所以容量无穷。再添加源点和汇点就建完了，汇点连接每个插座，源点连接每个设备，每边容量为1。使用增广路算法就得出解了。注意要空一行。
很不愿意用结构体的，但是既然用起来这么方便，就用着吧，有些题是需要用结构体的。
//#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=+;
unordered_map<string, int> has;
vector<int> dev;
vector<int> plug;
vector<pii> chg;
vector<int> vect[];
int path[];
int flow[];
int edge_cnt; struct node
{
int from;
int to;
int cap;
int flo;
}edge[N]; void add_node(int fr,int t,int ca,int fl)
{
edge[edge_cnt].from=fr;
edge[edge_cnt].to=t;
edge[edge_cnt].cap=ca;
edge[edge_cnt].flo=fl;
vect[fr].push_back(edge_cnt++);
} void build_graph(int n, int m, int k, int hui)
{
//每种型号的插口是个点
for(int i=; i<chg.size(); i++) //转换器自身
{
int in=chg[i].first;
int out=chg[i].second; add_node(in, out, INF, ); //应该是四条边
add_node(out, in, , );
} for(int i=; i<dev.size(); i++) //添加源点0号
{
int in=dev[i];
add_node(, in, , );
add_node(in, , , );
} for(int i=; i<plug.size(); i++) //添加汇点
{
int out=plug[i];
add_node(out, hui, , );
add_node(hui, out, , );
}
} int bfs(int s,int e)
{
deque<int> que;
que.push_back(s);
flow[s]=INF;
while(!que.empty())
{
int x=que.front();
que.pop_front();
for(int i=; i<vect[x].size(); i++)
{
node e=edge[vect[x][i]];
if(!flow[e.to] && e.cap>e.flo)
{
path[e.to]=vect[x][i];
flow[e.to]=min(flow[e.from],e.cap-e.flo);
que.push_back(e.to);
}
}
if(flow[e]) return flow[e];
}
return flow[e];
} int cal(int s, int e)
{
int big_flow=;
while(true)
{
memset(flow,,sizeof(flow));
memset(path,,sizeof(path)); int tmp=bfs(s,e);
if(!tmp) return big_flow;
big_flow+=tmp;//统计流 int ed=e;
while(ed!=s)
{
int t=path[ed];
edge[t].flo+=tmp;
edge[t^].flo-=tmp;
ed=edge[t].from;
}
}
} int main()
{
freopen("input.txt", "r", stdin);
int n, m, t, k;
char s3[], s4[];
string s1,s2;
cin>>t;
while(t--)
{
has.clear();
dev.clear();
plug.clear();
chg.clear(); memset(edge,,sizeof(edge));
edge_cnt=;
for(int i=; i<; i++) vect[i].clear();
int num=; scanf("%d",&n); //插座
for(int i=; i<n; i++)
{
scanf("%s",s3);
s1=s3;
if(!has[s1]) has[s1]=++num;
plug.push_back(has[s1]);
} scanf("%d",&m); //设备
for(int i=; i<m; i++)
{
scanf("%s%s",s3,s4);
s1=s3;
s2=s4;
if(!has[s2]) has[s2]=++num;
dev.push_back(has[s2]);
} scanf("%d",&k); //转换头
for(int i=; i<k; i++)
{
scanf("%s%s",s3,s4);
s1=s3;
s2=s4;
if(!has[s1]) has[s1]=++num;
if(!has[s2]) has[s2]=++num;
chg.push_back(make_pair(has[s1], has[s2]));
}
build_graph(n, m, k, num+);
printf("%d\n",m-cal(, num+));
if(t) printf("\n");
}
return ;
} AC代码
AC代码
//#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define INF 0x7f7f7f7f
using namespace std;
const int N=+;
unordered_map<string, int> has;
vector<int> dev;
vector<int> plug;
vector<pii> chg;
vector<int> vect[];
int path[];
int flow[];
int edge_cnt; struct node
{
int from;
int to;
int cap;
int flo;
}edge[N]; void add_node(int fr,int t,int ca,int fl)
{
edge[edge_cnt].from=fr;
edge[edge_cnt].to=t;
edge[edge_cnt].cap=ca;
edge[edge_cnt].flo=fl;
vect[fr].push_back(edge_cnt++);
} void build_graph(int n, int m, int k, int hui)
{
//每种型号的插口是个点
for(int i=; i<chg.size(); i++) //转换器自身
{
int in=chg[i].first;
int out=chg[i].second; add_node(in, out, INF, ); //应该是四条边
add_node(out, in, , );
} for(int i=; i<dev.size(); i++) //添加源点0号
{
int in=dev[i];
add_node(, in, , );
add_node(in, , , );
} for(int i=; i<plug.size(); i++) //添加汇点
{
int out=plug[i];
add_node(out, hui, , );
add_node(hui, out, , );
}
} int spfa(int s,int e)
{
deque<int> que;
que.push_back(s);
flow[s]=INF;
while(!que.empty())
{
int x=que.front();
que.pop_front();
for(int i=; i<vect[x].size(); i++)
{
node e=edge[vect[x][i]];
if(!flow[e.to] && e.cap>e.flo)
{
path[e.to]=vect[x][i];
flow[e.to]=min(flow[e.from],e.cap-e.flo);
que.push_back(e.to);
}
}
if(flow[e]) return flow[e];
}
return flow[e];
} int cal(int s, int e)
{
int big_flow=;
while(true)
{
memset(flow,,sizeof(flow));
memset(path,,sizeof(path)); int tmp=spfa(s,e);
if(!tmp) return big_flow;
big_flow+=tmp;//统计流 int ed=e;
while(ed!=s)
{
int t=path[ed];
edge[t].flo+=tmp;
edge[t^].flo-=tmp;
ed=edge[t].from;
}
}
} int main()
{
freopen("input.txt", "r", stdin);
int n, m, t, k;
char s3[], s4[];
string s1,s2;
cin>>t;
while(t--)
{
has.clear();
dev.clear();
plug.clear();
chg.clear(); memset(edge,,sizeof(edge));
edge_cnt=;
for(int i=; i<; i++) vect[i].clear();
int num=; scanf("%d",&n); //插座
for(int i=; i<n; i++)
{
scanf("%s",s3);
s1=s3;
if(!has[s1]) has[s1]=++num;
plug.push_back(has[s1]);
} scanf("%d",&m); //设备
for(int i=; i<m; i++)
{
scanf("%s%s",s3,s4);
s1=s3;
s2=s4;
if(!has[s2]) has[s2]=++num;
dev.push_back(has[s2]);
} scanf("%d",&k); //转换头
for(int i=; i<k; i++)
{
scanf("%s%s",s3,s4);
s1=s3;
s2=s4;
if(!has[s1]) has[s1]=++num;
if(!has[s2]) has[s2]=++num;
chg.push_back(make_pair(has[s1], has[s2]));
}
build_graph(n, m, k, num+);
printf("%d\n",m-cal(, num+));
if(t) printf("\n");
}
return ;
}
AC代码