先看一下匈牙利算法的dfs实现，很简洁
//二分匹配模板
bool g_map[MAX_N][MAX_N];
int r[MAX_N];
int l[MAX_N];
bool used[MAX_N];
int n;
bool path(int u,int n){
for(int v = 0 ; v < n ; v++){
if(g_map[u][v] && !used[v]){
used[v] = true;
if(r[v] == -1 || path(r[v],n)){
l[u] = v;
r[v] = u;
return true;
}
}
}
return false;
}
int bin_match(int n){
int res = 0;
memset(r,-1,sizeof(r));
memset(l,-1,sizeof(l));
for(int i = 0 ; i < n ; i++){
memset(used,false,sizeof(used));
if(l[i] == -1){
if(path(i,n)) res++;
}
}
return res;
}
n代表了左右两侧的点的数目，这里假设相等，点采用0,1,---n-1为标号。
使用时，需要保证g_map已经保存了两侧点的链接关系。标号采用如上安排。
注：dfs找增广路的实现很简单
path(int u),左侧点不用设置used标志，因为左侧点的寻找是根据匹配关系找到的，第一个左侧点保证l[i] == -1，没有匹配，递归过程中的path调用都是从左侧点开始的，而左侧点则是根据右侧点的匹配点决定的，不用寻找。
poj1043 What's In A Name?
根据是否存在可能对应关系构图，然后求二分图最大匹配，最好枚举匹配上的边，看该边去掉，最大匹
配数是否改变。
1.注意构图的时候，初始化是默认所有的点之间都有边相连，然后通过输入不断排除这样的相连关系。
在这个题目中，相连的意义代表了一种id与name相对应的一种可能性。
比如发现当前发出的一个消息m中包含id1，则该id只可能与当前出现的那些name集合中的name有可能对
应，这时就需要排除掉不在当前出现的那些name集合中的name与该id1的连接。
如果是开始默认无边相连，而在发现id1的时候，建立起id1与当前出现的那些name集合中的name的连接
边。这样可能存在如下问题，就是比如id1可能两次出现，比如
{name1,name2}:id1
{name2,name3}:id1
这样id1第二次出现，我们不仅要完成构造id1与name3的连接边，还要解除先前构造起来的与name1之间
的连接关系，因为显然id1不可能是对应name1的。
2.首先求出最大匹配，然后逐个最大匹配中的每个匹配，如果去掉该边，最大匹配不变，说明该对应关
系不确定，否则对应关系唯一。
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
#define MAX_N 30
#define debug
//#undef debug
using namespace std;
//二分匹配模板
bool g_map[MAX_N][MAX_N];
int r[MAX_N];
int l[MAX_N];
bool used[MAX_N];
int n;
bool path(int u,int n){
for(int v = 0 ; v < n ; v++){
if(g_map[u][v] && !used[v]){
used[v] = true;
if(r[v] == -1 || path(r[v],n)){
l[u] = v;
r[v] = u;
return true;
}
}
}
return false;
}
int bin_match(int n){
int res = 0;
memset(r,-1,sizeof(r));
memset(l,-1,sizeof(l));
for(int i = 0 ; i < n ; i++){
memset(used,false,sizeof(used));
if(l[i] == -1){
if(path(i,n)) res++;
}
}
return res;
}
map<string,int> id_set;
map<string,int> name_set;
string ids[MAX_N];
void init(){
cin >> n;
string id;
for(int i = 0 ; i < n ; i++){
cin >> id;
ids[i] = id;
id_set[id] = i;
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++)
g_map[i][j] = true;
}
string type,name_id;
int name_num = 0;
bool is_name_in[MAX_N]={false};
while(cin >> type && type[0] != 'Q'){
cin >> name_id;
if(type[0] == 'E'){
if(name_set.find(name_id) == name_set.end()){
name_set[name_id] = name_num;
is_name_in[name_num] = true;
name_num++;
}
else{
int index = name_set[name_id];
is_name_in[index] = true;
}
}
else if(type[0] == 'L'){
int index = name_set[name_id];
is_name_in[index] = false;
}
else if(type[0] == 'M'){
int id_index = id_set[name_id];
for(int j = 0 ; j < n ; j++){
if(is_name_in[j] == false)
g_map[id_index][j] = false;
}
}
}//end of while
}
//
void debug_print(bool g_map[MAX_N][MAX_N],int n){
#ifdef debug
cout << "ids:"<<endl;
for(map<string,int>::const_iterator p = id_set.begin(); p != id_set.end();p++){
cout << p-> first << ":"<<p-> second<<endl;
}
cout << "name:"<<endl;
for(map<string,int>::const_iterator p = name_set.begin(); p != name_set.end();p++){
cout << p-> first << ":"<<p-> second<<endl;
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
cout << g_map[i][j] <<" ";
}
cout << endl;
}
#endif
}
int main()
{
init();
//debug_print(g_map,n);
int match_num = bin_match(n);
int id_of_name[MAX_N];
for(int i = 0 ; i < n ; i++)
id_of_name[i] = r[i];
for(int i = 0 ; i < n ; i++){
if(id_of_name[i] != -1){
g_map[id_of_name[i]][i]=false;
int temp = bin_match(n);
g_map[id_of_name[i]][i]=true;
if(temp == match_num){
id_of_name[i] = -1;
}
}
}
for(map<string,int>::const_iterator p = name_set.begin(); p != name_set.end();p++){
int index = p->second;
if(id_of_name[index] == -1) cout << p-> first << ":"<<"???"<<endl;
else cout << p-> first << ":"<<ids[id_of_name[index]]<<endl;
}
return 0;
}
评论