A Plug for UNIX UVA - 753（网络流）

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0,f = 1; char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar();}
    while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}

const int N = 500;
const int INF = 0x3f3f3f3f;
int n,m,k,tol,cnt;
map<string,int> mp;
vector<int> a;
vector<int> b;
bool f[N][N];
struct Edge { int v,f,next; } edge[N * 2];
int head[N],level[N],iter[N];

inline void init() {
    mp.clear();
    a.clear();
    b.clear();
    tol = cnt = 0;
    memset(f,0,sizeof(f));
    memset(head,-1,sizeof(head));
}

inline void addedge(int u,int v,int f) {
    edge[cnt].v = v; edge[cnt].next = head[u]; edge[cnt].f = f; head[u] = cnt++;
}

void floyd() {
    for (int k = 1; k <= tol; k++) {
        for (int i = 1; i <= tol; i++) {
            for (int j = 1; j <= tol; j++) {
                f[i][j] = f[i][j] || (f[i][k] && f[k][j]);
            }
        }
    }
}

bool bfs(int s,int t) {
    for (int i = 0; i <= t; i++) iter[i] = head[i],level[i] = -1;
    level[s] = 0;
    queue<int> que;
    que.push(s);
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = head[u]; ~i; i = edge[i].next) {
            int v = edge[i].v,f = edge[i].f;
            if (f > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v); 
            }
        }
    }
    return level[t] != -1;
}

int dfs(int u,int t,int f) {
    if (!f || u == t) return f;
    int flow = 0,w;
    for (int i = iter[u]; ~i; i = edge[i].next) {
        iter[u] = i;
        int v = edge[i].v;
        if (level[v] == level[u] + 1 && edge[i].f > 0) {
            w = dfs(v,t,min(f,edge[i].f));
            if (w == 0) continue;
            f -= w;
            edge[i].f -= w;
            edge[i^1].f += w;
            flow += w;
            if (f <= 0) break;   
        }
    }
    return flow;
}

int dinic(int s,int t) {
    int ans = 0;
    while (bfs(s,t)) ans += dfs(s,INF);
    return ans;
}

int main() {
    int T = read();
    while (T--) {
        init();
        n = read();
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            mp[s] = i;
            a.emplace_back(i);
            tol++;
        }
        m = read();
        for (int i = 1; i <= m; i++) {
            string str1,s;
            cin >> str1 >> s;
            if (!mp.count(s)) {
                mp[s] = ++tol;   
            }
            b.emplace_back(mp[s]);
        }
        k = read();
        for (int i = 1; i <= k; i++) {
            string s1,s2;
            cin >> s1 >> s2;
            if (!mp.count(s1)) mp[s1] = ++tol;
            if (!mp.count(s2)) mp[s2] = ++tol;
            f[mp[s1]][mp[s2]] = 1;
        }
        for (int i = 1; i <= tol; i++) f[i][i] = 1;
        floyd();
        for (int i = 1; i <= m; i++) {
            addedge(0,i,1);
            addedge(i,0);
        }
        for (int i = 1; i <= n; i++) {
            addedge(m + i,n + m + 1,1);
            addedge(n + m + 1,m + i,0);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!f[b[i]][a[j]]) continue;
                addedge(i + 1,m + j + 1,INF);
                addedge(m + j + 1,i + 1,0);   
            }
        }
        printf("%dn",m - dinic(0,n + m + 1));
        if (T) puts("");
    } 
    return 0;
}