题意：n个插座，m个设备及其插头类型，k种转换器，没有转换器的情况下插头只能插到类型名称相同的插座中，问最少剩几个不匹配的设备

lrj紫书里面讲得挺好的。

先跑一遍floyd，看看插头类型a能否转换为b

然后构造网络

源点为0， 汇点为n + m + 1，源点连插头 容量为1，插座连汇点，容量为1

插头和插座能互相转换的容量为INF，跑一遍最大流 m - 最大流就是答案

顺便粘一下dinic的板子

#include 
      
       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
       
         mp;vector
        
          a;vector
         
           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
          
            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, t, 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, 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("%d\n", m - dinic(0, n + m + 1));        if (T) puts("");    }     return 0;}