登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

二分图最大匹配-dfs寻路  

2008-12-22 14:15:26|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

先看一下匈牙利算法的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;
}


 

  评论这张
 
阅读(1112)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018