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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

二分图最大匹配(部分转载)  

2014-02-23 16:42:51|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
USACO中有一题是最大匹配,用网络流可以A,然而此处可谓是大材小用,时间较慢。于是我学了一种新的算法,只需要N2的效率,空间是2N,那就是二分图----

 

1/置已匹配的边集为空匈牙利算法的实现过程(类似DFS):
2/由某一集合中的节点X1出发寻找一条交错轨!
3/取反!使得匹配边集变大! 
4/继续2过程,对X中的所有元素进行相同操作!
写成伪代码之后就如下:  bool 寻找从k出发的对应项出的可增广路
 {   while (从邻接表中列举k能关联到顶点j)  
  {    if (j不在增广路上)   
   { 把j加入增广路;     
 if (j是未盖点 或者 从j的对应项出发有可增广路)   
     { 修改j的对应项为k;     
     则从k的对应项出有可增广路,返回true;   
     }  
   }  
  }   则从k的对应项出没有可增广路,返回false; 
 }    
void 匈牙利hungary()
{  
 for i->1 to n  
 {    if (则从i的对应项出有可增广路)  
       匹配数++;
  }   输出 匹配数; 
} 该算法的复杂度分析:  时间复杂度:邻接矩阵:O(N^3)邻接表:O(N*M)
           空间复杂度:邻接矩阵:O(N^2)邻接表:O(N+M)   
           关于前面例题的点拨: 
       例1:将棋盘染色,成为国际象棋棋盘一样的颜色,然后将相邻的且两色块都可以放骨牌的顶点用边连起来,可以通过性质证明得到了一张二分图,然后对该二分图求最大匹配!
       例2:猎人的目的是打到所有的鸟,言外之 意不就是说所有有鸟的方格都要有子弹经过吗?方 格是什么?方格不就是由行和列来唯一确定的吗? 那么问题是不是就可以转化为用多少颗子弹能把所有的行和列都穿过,如果我们再联想一下,
       把子弹 看作是边,那么问题是不是就变成了最少用多少条 边可以把所有的行和列相连,把行看作是一部分点, 列看作另一部分点(注意行和列只考虑有鸟的方格) 这样,最大匹配数即猎人要打的枪数.标准代码(pascal):(只贴出匈牙利算法的标程,其余自行脑补!)
  Ps:红色部分为关键部分!
  const   MXN=1000; var    g:array[1..MXN,1..MXN] of boolean; 
  p:array[1..MXN] of longint; 
  vis:array[1..MXN] of boolean;
  n,m,k,i,ans,x,y:longint;
  function find(i:longint):boolean;
  var    j:longint; 
  begin     
  for j:=1 to m do 
   if (g[i,j]) and (not vis[j]) then 
   begin 
   vis[j]:=true;          
   if (p[j]=0) or (find(p[j])) then begin  
            p[j]:=i;          
             exit(true);        
              end;      
              end;     
              exit(false);
                 end;
   begin    
   assign(input,'work.in');reset(input);  
    assign(output,'work.out');rewrite(output);   
    readln(n,m,k);    
    for i:=1 to k do begin    
     readln(x,y);    
      g[x,y]:=true;   
      end;    for i:=1 to n do begin 
           fillchar(vis,sizeof(vis),0);   
             if find(i) then inc(ans);   
             end;    writeln(ans);  
             //for i:=1 to n do if p[i]>0 then writeln(p[i],' -----> ',i);   close(input);close(output); 
    end.
  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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