题目链接

【题意】

有若干个电器设备需要不同的适配器才能接上电源，现在你要让尽可能多的设备接上电源。首先你手中有n个适配器和适配器的型号，再告诉你有m个电器和他们分别对应的适配器的型号，最后还有一个商店提供k个不同类型的转换器，转换是单向的A B表示能把A接口转换成B接口，转换器数量是没有限制。求最少有多少设备无法连接电源.

【思路】

最大流模板题，将不同类型的设备和插头抽象成结点，转换器的转换关系抽象成有向边，源点与设备相连，插座与汇点相连，跑一次最大流即可

#include
    
     using namespace std;const int inf=2e9;const int maxn=550;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,s,t;    vector
     
       edges;    vector
      
        g[maxn];    bool vis[maxn];    int d[maxn];    int cur[maxn];    void init(int n){        this->n=n;        for(int i=0;i<=n;i++) g[i].clear();        edges.clear();    }    void add(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(){        memset(vis,0,sizeof(vis));        queue
       
         que;        que.push(s);        d[s]=0;        vis[s]=1;        while(!que.empty()){            int x=que.front();que.pop();            for(int i=0;i
        
         e.flow){                    vis[e.to]=1;                    d[e.to]=d[x]+1;                    que.push(e.to);                }            }        }        return vis[t];    }    int DFS(int x,int a){        if(x==t || a==0) return a;        int flow=0,f;        for(int& i=cur[x];i
         
          0){ e.flow+=f; edges[g[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0) break; } } return flow; } int Maxflow(int s,int t){ this->s=s;this->t=t; int flow=0; while(BFS()){ memset(cur,0,sizeof(cur)); flow+=DFS(s,inf); } return flow; }};int n,m,k;char name[30],str[30];map
          
            mp;Dinic solver;int main(){ int T; int s=0,t=500; scanf("%d",&T); while(T--){ mp.clear(); solver.init(520); int id=0; scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%s",str); string x=(string)str; if(mp[x]==0) mp[x]=++id; solver.add(mp[x],t,1); } scanf("%d",&m); for(int i=1;i<=m;++i){ scanf("%s%s",name,str); string x=(string)str; if(mp[x]==0) mp[x]=++id; solver.add(s,mp[x],1); } scanf("%d",&k); for(int i=1;i<=k;++i){ scanf("%s%s",name,str); string x=(string)name; string y=(string)str; if(mp[x]==0) mp[x]=++id; if(mp[y]==0) mp[y]=++id; solver.add(mp[x],mp[y],inf); } int ans=solver.Maxflow(s,t); ans=m-ans; printf("%d\n",ans); if(T) puts(""); } return 0;}