hdu 1526 poj 1087最大流

好恶心的题目，题面那么长，害我折腾了几个小时。。。刚开始是在杭电做的这题，打完代码以后交不过，不得已查解题报告，才发现poj上也有这题。看了别人的解题报告之后才发现自己理解错了。于是推倒重来，重新写，可还是不过。问了问金牛，才发现居然还是理解错了题目，晕死啊。。。。最后根据那组数据调了一会儿，就过了。

我的做法跟网上别人的做法一样，用的最大流。建图的时候，加一个源点一个汇点，源点连插座，流量为1，插座连电器，流量为1，电器连汇点，流量为1，然后如果插座A能通过适配器转换成插座B，就连A到B，流量无穷大。最大流就是最多能插上的电器数了。

/*
 * hdu1526/win.cpp
 * Created on: 2013-1-4
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
typedef int typec;
const typec inf = 0x7fffffff;
const int MAXE = 300000;
const int MAXN = 700;
const int MAXCUR = 500;
const int END = 650;
const int PY = 520;

typedef struct {
    int x, y, nxt;
    typec c;
} Edge;
Edge bf[MAXE];
int ne, head[MAXN], cur[MAXN], ps[MAXN], dep[MAXN];
void addedge(int x, int y, typec 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++;
}
typec flow(int n, int s, int t) {
    typec 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;
}
int graph[MAXCUR][MAXCUR];
void Floyd(int N) {
    int i, j, k;
    for (k = 0; k < N; k++) {
        for (i = 0; i < N; i++) {
            for (j = 0; j < N; j++) {
                if(graph[i][k] < graph[i][j] - graph[k][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}
int work() {
    char str[100], str2[100];
    map<string, int> mymap;
    int n, m, k, curnamenum;
    ne = 2;
    memset(head, 0, sizeof(head));
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        addedge(0, i, 1);
        scanf("%s", str);
        mymap[string(str)] = i;
    }
    curnamenum = n;
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        addedge(PY + i, END, 1);
        scanf("%s%s", str2, str);
        if(mymap.find(string(str)) == mymap.end()) {
            mymap[string(str)] = ++curnamenum;
        }
        addedge(mymap[string(str)], PY+ i, 1);
    }
    scanf("%d", &k);
    fill_n(*graph, MAXCUR * MAXCUR, inf);
    for(int i = 0; i < MAXCUR; i++) {
        graph[i][i] = 0;
    }
    for(int i = 0; i < k; i++) {
        scanf("%s%s", str, str2);
        if(mymap.find(string(str)) == mymap.end()) {
            mymap[string(str)] = ++curnamenum;
        }
        if(mymap.find(string(str2)) == mymap.end()) {
            mymap[string(str2)] = ++curnamenum;
        }
        int b = mymap[string(str)];
        int a = mymap[string(str2)];
        graph[a - 1][b - 1] = 1;
    }
    Floyd(curnamenum);
    for(int i = 1; i <= curnamenum; i++) {
        for(int j = 1; j <= curnamenum; j++) {
            if(i != j && graph[i - 1][j - 1] < inf) {
                addedge(i, j, inf);
            }
        }
    }
    return m - flow(END + 1, 0, END);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        printf("%d\n", work());
        if(T) {
            putchar('\n');
        }
    }
    return 0;
}