Description
and bureaucratic as possible.
Since the room was designed to accommodate reporters and journalists from around the world, it is equipped with electrical receptacles to suit the different shapes of plugs and voltages used by appliances in all of the countries that existed when the room was
built. Unfortunately, the room was built many years ago when reporters used very few electric and electronic devices and is equipped with only one receptacle of each type. These days, like everyone else, reporters require many such devices to do their jobs:
laptops, cell phones, tape recorders, pagers, coffee pots, microwave ovens, blow dryers, curling
irons, tooth brushes, etc. Naturally, many of these devices can operate on batteries, but since the meeting is likely to be long and tedious, you want to be able to plug in as many as you can.
Before the meeting begins, you gather up all the devices that the reporters would like to use, and attempt to set them up. You notice that some of the devices use plugs for which there is no receptacle. You wonder if these devices are from countries that didn't
exist when the room was built. For some receptacles, there are several devices that use the corresponding plug. For other receptacles, there are no devices that use the corresponding plug.
In order to try to solve the problem you visit a nearby parts supply store. The store sells adapters that allow one type of plug to be used in a different type of outlet. Moreover, adapters are allowed to be plugged into other adapters. The store does not have
adapters for all possible combinations of plugs and receptacles, but there is essentially an unlimited supply of the ones they do have.
Input
type consists of a string of at most 24 alphanumeric characters. The next line contains a single positive integer m (1 <= m <= 100) indicating the number of devices you would like to plug in. Each of the next m lines lists the name of a device followed by
the type of plug it uses (which is identical to the type of receptacle it requires). A device name is a string of at most 24 alphanumeric
characters. No two devices will have exactly the same name. The plug type is separated from the device name by a space. The next line contains a single positive integer k (1 <= k <= 100) indicating the number of different varieties of adapters that are available.
Each of the next k lines describes a variety of adapter, giving the type of receptacle provided by the adapter, followed by a space, followed by the type of plug.
Output
Sample Input
4 A B C D 5 laptop B phone C pager B clock B comb X 3 B X X A X D
Sample Output
1
//
将每一种插头看成一个点,每一个用电器看成一个点,然后构图.用电器可以插入对应的插座,所以该用电器这个点可以和该插座对应的插头种类这个点连线,且该连线的权值为1,而由于适配器有无数个,所以将适配器的插孔和所对应的插头或适配器的插头连线,权值为INF,然后再加上虚源点和虚汇点,令虚源点和所有用电器所对应的节点连接,且连接所得到的边的权值为1,n个插座插头所对应的节点与虚汇点相连接,且置连接后得到的边的权值为1
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
using namespace std;
const int inf=(1<<28);//不要开到(1<<30)
const int point_num=550;//300不够
int cap[point_num][point_num],dist[point_num],gap[point_num];//初始化见main里面
int s0,t0,n;//源,汇和点数
int find_path(int p,int limit=0x3f3f3f3f)
{
if(p==t0) return limit;
for(int i=0;i<n;i++)
if(dist[p]==dist[i]+1 && cap[p][i]>0)
{
int t=find_path(i,min(cap[p][i],limit));
if(t<0) return t;
if(t>0)
{
cap[p][i]-=t;
cap[i][p]+=t;
return t;
}
}
int label=n;
for(int i=0;i<n;i++) if(cap[p][i]>0) label=min(label,dist[i]+1);
if(--gap[dist[p]]==0 || dist[s0]>=n ) return -1;
++gap[dist[p]=label];
return 0;
}
int sap()
{
//初始化s,t
s0=0,t0=n-1;
int t=0,maxflow=0;
gap[0]=n;
while((t=find_path(s0))>=0) maxflow+=t;
return maxflow;
}
char str[300];
int s[300],t[300];
int x[300],y[300];
int main()
{
int k,c,m;
while(scanf("%d",&k)==1)
{
map<string,int> q;
n=0;
//初始化
memset(cap,0,sizeof(cap));
memset(dist,0,sizeof(dist));
memset(gap,0,sizeof(gap));
//初始化cap
for(int i=0;i<k;i++)//插座
{
scanf("%s",str);
q[str]=++n;
cap[0][n]=1;
}
scanf("%d",&c);//设备
for(int i=0;i<c;i++)
{
scanf("%s",str);
q[str]=++n;s[i]=n;
scanf("%s",str);
if(q[str]==0) q[str]=++n;
t[i]=q[str];
}
scanf("%d",&m);//转换器
for(int i=0;i<m;i++)
{
scanf("%s",str);
if(q[str]==0) q[str]=++n;
x[i]=q[str];
scanf("%s",str);
if(q[str]==0) q[str]=++n;
y[i]=q[str];
}
for(int i=0;i<c;i++)
{
cap[s[i]][n+1]=1;
cap[t[i]][s[i]]=1;
}
for(int i=0;i<m;i++)
{
cap[y[i]][x[i]]=inf;//important inf 如果是1会错误
}
n+=2;
int cnt=sap();
printf("%d\n",c-cnt);
}
return 0;
}