水题

注意建图,转换器是无限的。另外不能建设备。会t
##代码如下

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<set>
#include<map>
using namespace std;
const int max_n = 500;
const int max_m = 1000;
const int inf = 2e9;
struct edge
{
    int to, cap, rev, next;
}E[max_m * 2];
int head[max_n];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = 0;
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}

int iter[max_n];
int dist[max_n];
bool searchpath(int s, int t) {
    fill(dist, dist + max_n, -1);
    queue<int> que;dist[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}

int matchpath(int u, int t, int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap <= 0)continue;
        int d = matchpath(e.to, t, min(e.cap, f));
        if (d > 0) {
            e.cap -= d;
            E[e.rev].cap += d;
            return d;
        }
    }return false;
}

int dinic(int s, int t) {
    int flow = 0;int f;
    while (searchpath(s, t)) {
        for (int i = 1;i < max_n;i++)iter[i] = head[i];
        while (f = matchpath(s, t, inf))
            flow += f;
    }return flow;
}


int n, m, k;
string a[max_n], b[max_n], c[max_n][2];
string d[max_n];
int main() {
    ios::sync_with_stdio(0);
    cin >> n;
    map<string, int> mp;int tot = 0;
    for (int i = 1;i <= n;++i) {
        cin >> a[i];
        if (mp.find(a[i]) == mp.end())mp[a[i]] = ++tot;
    }cin >> m;
    for (int i = 1;i <= m;++i) {
        cin >> d[i] >> b[i];
        if (mp.find(b[i]) == mp.end())mp[b[i]] = ++tot;
    }cin >> k;
    for (int i = 1;i <= k;++i) {
        cin >> c[i][0] >> c[i][1];
        if (mp.find(c[i][0]) == mp.end())mp[c[i][0]] = ++tot;
        if (mp.find(c[i][1]) == mp.end())mp[c[i][1]] = ++tot;
    }int start = tot + 1;int ed = start + 1;
    for (int i = 1;i <= n;++i)add(start, mp[a[i]], 1);
    for (int i = 1;i <= m;++i) {
        add(mp[b[i]], ed, 1);
    }for (int i = 1;i <= k;++i)
        add(mp[c[i][1]], mp[c[i][0]], inf);
    cout << m - dinic(start, ed) << endl;
}