最大流

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; #define N 505 #define E 1005 #define inf 0x3f3f3f3f #define maxl 35 struct edge {
     int x, y, nxt; int c; } bf[E]; int ne, head[N], cur[N], ps[N], dep[N]; char name1[N][maxl], name2[N][maxl]; int s, t; int n, m, k; int getid(int &n, char name[][maxl], char *st) {
     for (int i = 0; i < n; i++) if (strcmp(st, name[i]) == 0) return i;     strcpy(name[n++], st); return n - 1; } void addedge(int x,int y, int c) {
         bf[ne].x = x;     bf[ne].y = y;     bf[ne].c = c;     bf[ne].nxt = head[x];     head[x] = ne++;     bf[ne].x = y;     bf[ne].y = x;     bf[ne].c = 0;     bf[ne].nxt = head[y];     head[y] = ne++; } int flow(int n, int s,  int t) {
     int tr, res = 0; int i, j, k, f, r, top; while (1)     {
             memset(dep, -1, n * sizeof(int)); for (f = dep[ps[0] = s] = 0, r = 1; f != r;) for (i = ps[f++], j = head[i]; j; j = bf[j].nxt)             {
     if (bf[j].c && -1 == dep[k = bf[j].y])                 {
                         dep[k] = dep[i] + 1; ps[r++] = k; if (k == t)                     {
                             f = r; break;                     }                 }             } if (-1 == dep[t]) break;         memcpy(cur, head, n * sizeof(int)); for (i = s, top = 0;;)         {
     if (i == t)             {
     for (k = 0, tr = inf; k < top; ++k) if (bf[ps[k]].c < tr)                         tr = bf[ps[f = k]].c; for (k = 0; k < top; ++k)                     bf[ps[k]].c -= tr, bf[ps[k]^1].c += tr;                 res += tr;                 i = bf[ps[top = f]].x;             } for (j = cur[i]; cur[i]; j = cur[i] = bf[cur[i]].nxt) if (bf[j].c && dep[i] + 1 == dep[bf[j].y]) break; if (cur[i])             {
                     ps[top++] = cur[i];                 i = bf[cur[i]].y;             } else             {
     if (0 == top) break;                 dep[i] = -1; i = bf[ps[--top]].x;             }         }     } return res; } void input() {
     char st[maxl]; char st1[maxl]; int x;     scanf("%d", &n);     s = 0;     t = 1;     x = n; for (int i = 0; i < n; i++)         scanf("%s", name1[i]);     scanf("%d", &m); for (int i = 0; i < m; i++)     {
             scanf("%s%s", name2[i], st);         addedge(i + 2, m + getid(n, name1, st) + 2, 1);         addedge(s, i + 2, 1);     }     scanf("%d", &k); for (int i = 0; i < k; i++)     {
             scanf("%s%s", st1, st);         addedge(getid(n, name1, st1) + m + 2, getid(n, name1, st) + m + 2, inf);     } for (int i = 0; i < x; i++)         addedge(i + m + 2, t, 1); } int main() {
     //freopen("t.txt", "r", stdin);     ne = 2;     memset(head, 0, sizeof(head));     input();     printf("%d\n", m - flow(n + m + 2, s, t)); return 0; }