POJ1043 What's In A Name? 反面构图+枚举边计算最大匹配

题意：给定一群人的姓名和昵称，给定了一些关系，现在要求判定姓名和昵称能够一一对应的有哪些？

解法：一开始直接使用藏匿点的所有人和邮件进行构边，再用删除来判定，结果出错，为什么呢？因为我们将藏匿点的所有人和邮件连边确定的就是一种可能关系，然而题目中还隐藏了许多的可能关系，比如某人在藏匿点但是没有发邮件，那么其和其他未出现的昵称之间存在可能关系。正确的解法是确定不可能关系，因为这样更加简单，在藏匿点外的人不可能与邮件有关系。初始化所有人和所有昵称都有关系，通过排除不可能的关系即确定了可能的关系。之后再枚举每一条边，将其删除看通过最大匹配是否减小来断定这条边是不是被唯一对应。注意：如果某一组名字-昵称关系是唯一确定的话，那么删除完所有的不可能情况后其在二分图中连到该昵称的边只有一条。

代码如下：

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <string>
#include <iostream>
using namespace std;

int N, idx;
char G[25][25], vis[25];
int match[25];
map<string, int>mp, mpID;
map<int,int>mp_ret;
set<int>st;
set<int>::iterator it;

int path(int u) {
    for (int i = 1; i <= N; ++i) {
        if (G[u][i] || vis[i]) continue;
        vis[i] = 1;
        if (!match[i] || path(match[i])) {
            match[i] = u;
            return 1;
        }
    }
    return 0;
}

int query() {
    int ret = 0;
    memset(match, 0, sizeof (match));
    for (int i = 1; i <= N; ++i) {
        memset(vis, 0, sizeof (vis));
        ret += path(i);
    }
    return ret;
}

void output() {
    map<string,int>::iterator it1, it2;
    for (it1 = mp.begin(); it1 != mp.end(); ++it1) {
        if (mp_ret.count(it1->second)) {
            for (it2 = mpID.begin(); it2 != mpID.end(); ++it2) {
                if (it2->second == mp_ret[it1->second])    {
                    cout << it1->first << ":" << it2->first << endl;
                    break;
                }
            }
        } else {
            cout << it1->first << ":???" << endl;
        }
    }
}

int main() {
    int T;
    char name[25], op[5];
    while (scanf("%d", &N) != EOF) {
        idx = 1;
        mp.clear(), mpID.clear();
        st.clear(), mp_ret.clear();
        memset(G, 0, sizeof (G));
        for (int i = 1; i <= N; ++i) {
            scanf("%s", name);
            mpID[name] = i; // 对字符串进行hash处理
        }
        while (scanf("%s", op), op[0] != 'Q') {
            if (op[0] == 'E') { // 进来的人名 
                scanf("%s", name);
                if (!mp.count(name)) {
                    mp[name] = idx++;
                }
                st.insert(mp[name]);
            }
            else if (op[0] == 'M') { // 发出去的是账户名 
                scanf("%s", name);
                char in[25] = {0};
                for (it = st.begin(); it != st.end(); ++it) { // 在藏匿点的所有人都和这封邮件连边
                    in[*it] = 1;
                }
                for (int i = 1; i <= N; ++i) {
                    if (!in[i]) G[i][mpID[name]] = 1; // 外面的人肯定与邮件无关
                }
            }
            else if (op[0] == 'L') {
                scanf("%s", name);
                it = st.find(mp[name]);
                st.erase(it);
            }
        }
        int Max = query(), t;
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (G[i][j]) continue;
                G[i][j] = 1;
                t = query();
                G[i][j] = 0;
                if (t < Max) {
                    mp_ret[i] = j;
                    break;
                }
            }
        }
        output();
    }
    return 0;    
}