题意:有插座以及用电器和适配器,用电器有插头,适配器本身有一个插孔和插头,它的作用是可以把别的插头插入到适合该适配器插孔的适配器,然后就可以用适配器的插头接到适合的插座,相当于转换插头的作用,每个插座只能插入一个插头,3种东西都最多有100个,但是任一种适配器可以有无限个(but there is essentially an unlimited supply of the ones they do have.),求解{zh1}不能完成充电的最小的用电器数目.

        用{zd0}流问题的增广路算法来求解该问题:将每一种插头看成一个点,每一个用电器看成一个点,然后构图.用电器可以插入对应的插座,所以该用电器这个点可以和该插座对应的插头种类这个点连线,且该连线的权值为1,而由于适配器有无数个,所以将适配器的插孔和所对应的插头或适配器的插头连线,权值为INF,然后再加上虚源点和虚汇点,令虚源点和所有用电器所对应的节点连接,且连接所得到的边的权值为1,n个插座插头所对应的节点与虚汇点相连接,且置连接后得到的边的权值为1.
#include<iostream>
#include<cstdlib>
#include<queue>
#include<string>
#include<map>
#include<algorithm>
using namespace std;

const int INF=1000000000;
const int MAXN=505;

int n, m, S, T;
int a[MAXN], p[MAXN], cap[MAXN][MAXN], flow[MAXN][MAXN];

map<string,int>mp;                                        //这里用map容器来进行字符串的处理

int main()
{

     int i,j,u,v,w,k,x,y,ans,t;
     queue<int>q;
     char s1[30],s2[30];
     string ss,s;
     while(scanf("%d",&n)!=EOF)
     {
        memset(flow,0,sizeof(flow));
        memset(cap,0,sizeof(cap));
        ans=0;                                              //{zd0}流值
        S=0;                                               //源点
        for(i=1;i<=n;i++)
        {
            scanf("%s",&s1);
            ss=s1;
            mp[ss]=i;
        }
        scanf("%d",&m);
        for(t=n,i=1;i<=m;i++)
        {
           scanf("%s%s",s1,s2);
           ss=s2;
           if(mp[ss]==0)                                //此时说明字符串ss是新增进来的节点
           {
              t++;
              mp[ss]=t;
           }
           cap[i][m+mp[ss]]=1;                          //注意这里将用电器从1到m开始编号,而插座所对应的节点从(m+1)开始编号
        }
        scanf("%d",&k);
        for(i=1;i<=k;i++)
        {
            scanf("%s%s",s1,s2);
            ss=s1;
            if(mp[ss]==0)                                //同理此时字符串s1是新增进来的节点
            {
              t++;
              mp[ss]=t;
            }
            ss=s2;
            if(mp[ss]==0)                               //同上
            {
              t++;
              mp[ss]=t;
            }
            s=s1;
            cap[m+mp[s]][m+mp[ss]]=INF;                //因为适配器可以有无数多个,所以将所对应的边的权值置为无穷大(开始这里一直置为1,错了几次不知道原因,后来看讨论才知道)
        }
        for(i=1;i<=m;i++)                                  //将虚源点到各用电器所对应的节点的距离置为1
           cap[S][i]=1;
        T=m+t+1;                                              //汇点
        for(i=1;i<=n;i++)                                     //将各充电器所对应的节点和虚汇点的距离置为1
           cap[m+i][T]=1;
        while(1)
        {
                memset(a,0,sizeof(a));
                a[S]=INF;
                q.push(S);
                while(!q.empty())                        //BFS找增光路径
                {
                                 u=q.front();
                                 q.pop();
                                 for(v=1;v<=T;v++)
                                   if(!a[v]&&cap[u][v]>flow[u][v])
                                    {
                                                  p[v]=u;
                                                  q.push(v);
                                                  a[v]=min(a[u],cap[u][v]-flow[u][v]);      //求最短路径上的最小残留量
                                    }
                }
                if(a[T]==0)                                                                          //找不到,则当前流已经是{zd0}流
                   break;
                for(u=T;u!=S;u=p[u])                                                         //从汇点往回走
                {
                    flow[p[u]][u]+=a[t];                                                          //更新正向流量
                    flow[u][p[u]]-=a[t];                                                            //更新方向流量
                }
                ans+=a[T];
        }
        printf("%d\n",m-ans);                                                                    //注意{zh1}输出的是不能完成充电的用电器的最小数目
     }
     system("pause");
     return 0;
}