学步园

#include <iostream>
#include <string>
#include <map>
#define VMAX 600
#define PMAX 800
using namespace std;

map<string, int> item;
map<string, int>::iterator it;
int n, n2, m, k;
int match;
int map1[PMAX][PMAX] = {0};    //关联图
int map2[VMAX][VMAX] = {0};    //精简图
int dev[VMAX];                 //设备对应的插头序号
int path[VMAX];                //增广路
int link[VMAX] = {0};        //匹配

int addplug(string plug)       //添加插头种类
{
    it = item.find(plug);
    if (it == item.end())      //找不到则添加
    {
        item.insert(pair<string, int> (plug, n2));
        n2++;
        return n2 - 1;
    }
    else                       //找到则返回序号
        return item[plug];
}

int find(int i)                //匈牙利算法
{
    for (int j = 1; j <= n; j++)
        if (map2[i][j] && !path[j])   //  i与j相连 &&  j不在当前增广路上
        {
            path[j] = 1;
            if (!link[j] || find(link[j]))
            {
                link[j] = i;
                return 1;
            }
        }
    return 0;
}

int main()
{
    int a, b;
    int i, j, k;
    string tmp1, tmp2;
 
    cin >> n;
    n2 = n;
    for (i = 0; i < n; i++)
    {
        cin >> tmp1;
        item.insert(pair<string, int> (tmp1, i));
    }
    cin >> m;
    for (i = 0; i < m; i++)
    {
        cin >> tmp1 >> tmp2;
        dev[i] = addplug(tmp2);
    }
    cin >> k;
    for (i = 0; i < k; i++)
    {
        cin >> tmp1 >> tmp2;
        a = addplug(tmp1);  //有可能风马牛, 否则直接map1[item[tmp1]][item[tmp2]] = 1
        b = addplug(tmp2);
        map1[a][b] = 1;
    }
    for (i = 0; i < n2; i++)
        for (j = 0; j < n2; j++)
        {
            if (i == j)
            {
                map1[i][i] = 1;
                continue;
            }
            if (map1[j][i])
                for (k = 0; k < n2; k++)
                    if (map1[i][k])
                        map1[j][k] = 1;
        }
    for (i = 0; i < m; i++)              //构造精简图
        for (j = 0; j < n; j++)
            if (map1[dev[i]][j])
                map2[i+1][j+1] = 1;
    match = 0;
    for (i = 1; i <= m; i++)
    {
        memset(path, 0, sizeof(path));   //清空增广路
        match += find(i);
    }
    printf("%d\n", m - match);
    return 0;
}