链接：http://poj.org/problem?

id=1087

题意：提供n种插座。每种插座仅仅有一个，有m个设备须要使用插座，告诉你设备名称以及使用的插座类型，有k种转换器。能够把某种插座类型转为还有一种，能够嵌套使用。比方有设备需使用第4种插座，如今仅仅有第一种插座，可是有两个转换器，1→3和3→4，则通过这两个转换器设备能够充电。每种转换器有无数个。现告诉你对应信息，求至少有多少个设备无法使用插座。

网络最大流单源点单汇点。是一道基础题，图建好就能套模板了。

关键是图怎么建。

还是自己设一个源点和一个汇点。源点出发到每种设备各有一条路径容量为1，如今已有的插座种类到汇点各有一条路径容量为1。反过来也行，最大流的值不会由于这个而改变。每种设备各有一个须要使用的插座类型。把这些设备和各自须要的插座连一条路径，容量为1。对于转换器，假设把a转为b，就在a和b之间连一条路径，容量为正无穷，图就建好了。

假设说的不够清楚。看了这个图也能一目了然。这是依据题目例子建的图：

#include<cstring>

#include<string>

#include<fstream>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cctype>

#include<algorithm>

#include<queue>

#include<map>

#include<set>

#include<vector>

#include<stack>

#include<ctime>

#include<cstdlib>

#include<functional>

#include<cmath>

using namespace std;

#define PI acos(-1.0)

#define MAXN 50100

#define eps 1e-7

#define INF 0x7FFFFFFF

#define seed 131

#define mod 1000000007

#define ll long long

#define ull unsigned ll

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

struct node{

    int u,w,next;

}edge[10100];

int head[210],vis[210],dist[210];

int n,m,k,src,sink,cnt;

int num1,num2;

map<string,int>mp;

void add_edge(int a,int b,int c){

    edge[cnt].u = b;

    edge[cnt].w = c;

    edge[cnt].next = head[a];

    head[a] = cnt++;

}

void bfs(){

    int i,j;

    memset(dist,0,sizeof(dist));

    queue<int>q;

    vis[src] = 1;

    q.push(src);

    while(!q.empty()){

        int tt = q.front();

        q.pop();

        for(i=head[tt];i!=-1;i=edge[i].next){

            if(!vis[edge[i].u]&&edge[i].w){

                dist[edge[i].u] = dist[tt] + 1;

                vis[edge[i].u] = 1;

                q.push(edge[i].u);

            }

        }

    }

}

int dfs(int u,int delta){

    int i,j;

    if(u==sink) return delta;

    int ret = 0;

    for(i=head[u];i!=-1;i=edge[i].next){

        if(edge[i].w&&dist[edge[i].u]==dist[u]+1){

            int dd = dfs(edge[i].u,min(delta,edge[i].w));

            edge[i].w -= dd;

            edge[i^1].w += dd;

            delta -= dd;

            ret += dd;

        }

    }

    return ret;

}

int maxflow(){

    int ret = 0;

    while(1){

        memset(vis,0,sizeof(vis));

        bfs();

        if(vis[sink]==0)    break;

        ret += dfs(src,INF);

    }

    return ret;

}

int main(){

    int i,j;

    string str1,str2;

    memset(head,-1,sizeof(head));

    num1 = 1;

    num2 = 101;

    cnt = 0;

    src = 0;

    sink = 205;

    scanf("%d",&n);

    for(i=0;i<n;i++){

        cin>>str1;

        mp[str1] = num1++;

        add_edge(mp[str1],sink,1);

        add_edge(sink,mp[str1],0);

    }

    scanf("%d",&m);

    for(i=0;i<m;i++){

        cin>>str1>>str2;

        mp[str1] = num2++;

        if(!mp[str2])   mp[str2] = num1++;

        add_edge(mp[str1],mp[str2],1);

        add_edge(mp[str2],mp[str1],0);

        add_edge(src,mp[str1],1);

        add_edge(mp[str1],src,0);

    }

    scanf("%d",&k);

    for(i=0;i<k;i++){

        cin>>str1>>str2;

        add_edge(mp[str1],mp[str2],INF);

        add_edge(mp[str2],mp[str1],0);

    }

    int ans = maxflow();

    printf("%d\n",m-ans);

    return 0;

}