• 匹配二分图的概念:
匹配:就是Match嘛,简单的说,一条边的两个顶点就是一个配对;严格的定义,设G=[V,E]是一个无向图,M属于U是G的若干边的集合,如果M中任意两条边都没有公共的端点[没有中间点,Match就是2,3就不叫匹配拉]OK,称M是一个匹配。
将M中的边最大化,使得在M中的顶点最多,这就是最大匹配问题
但匹配问题分为任意图的最大匹配,二分图的最大匹配。但任意图的最大匹配构造比较麻烦,因此,为了简化模型,就将二分图和匹配强行拉在一起。其实也起源于机器匹配,稳定婚姻[这个算法的描述太让人恶了,什么算法,参见算法艺术]等等非常出名的问题。
 
  • 关于二分图和其匹配的性质:
1,二分图的判定定理BFS的染双色可行或者距离只存在偶数路径。[必须秒杀]
2,二分图的最大匹配:存在两个非常出名的算法,匈牙利算法Hopcroft-Karp算法。网上的资料
Hall定理:对于二分图G=(x,y;e),存在一匹配M,使得x的所有顶点关于M饱和的充要条件:对x的任一子集A,和A邻接的点集p(A),则恒有:|p(A)|>=|A|.
必要性证明不说了。
充分性:若|p(A)|>=|A|,则和匈牙利算法一致,从x0出发,终点为未盖点,再次增广,直到找到x使得M饱和。
增广路经的定义这里省去。
 
下面详细描述和代码实现匈牙利算法[参考《实用》]:
  • 匈牙利算法
取G的一个未盖点作为树根,位于树的第0层。用递归方式设i-1层已经构造好了,再来构造第i层。当i为奇数时,将那些关联于第i-1层的一个顶点且不属于M的边,连同该边关联的另一个顶点一起连到树上;当i为偶数时,将那些关联于第i-1层的一个顶点且属于M的边,连同该边关联的另一个顶点。看代码要清晰的多!
实现方法:[代码在后] link表示其匹配点的索引,有些资料上是用ny,nx来表示的,但此处由于我在处理的时候只引出从X到Y的单向边,可以将两者合并。
1。DFS实现:
适用:稠密图,由于边多,dfs找增广路很快
复杂度:O(n^3)
2。BFS实现:
我的注释:用pre[1..nx]来表示X集的链路[匈牙利树的左枝],mk[1…n]来代表其生成树的顶点[防止同树的错误生长]
适用:稀疏二分图,边少,增广路短
复杂度:O(n^3)
 
  • Hopcroft-Karp算法[算法概述,HK算法还要好好研究下,今天状态不好,BFS没看的很清楚,DFS的版本大概懂了]
每次增广同时寻找多条不相交增广路,由Hopcroft和Karp于1973年提出。DFS和BFS均可以实现之![优点同上]
 
一个基本试验题目,主要用来实现上述的4种算法思路:
对于一个给定的二分图G(t,c;e),如图所示
测试数据:
10 12
1 6
1 7
1 8
2 6
2 9
2 10
3 6
3 7
4 8
4 9
4 10
5 6
 
1.DFS-Edmonds算法实现:
int eid=0, first[MAXN], link[MAXN], nv, ev;//for Edmonds DFS algorithm
bool used[MAXN];
//implementation for EdmondsDFS, 1965,here : link is just for Y set’s counterpart in X.
void EdmondsDFS(){
    memset((void*)link, 0xff, sizeof(link));
    int res=0;
    for(int i=1; i<=nv; i++){
        memset((void*)used, 0, sizeof(used)), res+=find(i);
    }
    cout<<res<<endl;
    for(int i=1; i<=nv; i++){
        if(link[i]!=-1) cout<<link[i]<<" "<<i<<endl;
    }
}

bool find(int s){
    for(int tmp=first[s]; tmp!=-1; tmp=es[tmp].next){
        if(!used[es[tmp].j]){
            used[es[tmp].j]=true;
            if(link[es[tmp].j]==-1||find(link[es[tmp].j])){//logic here : es[tmp].j is available, or could be extended
                link[es[tmp].j]=s; return true;
            }
        }
    }
    return false;
}

2.BFS-Edmonds算法实现:

//implementation for Edmonds, 1965, here link is for x’ y’s counter-part in bio-partite.
void EdmondsBFS(){
 memset((void*)mk, 0xff, sizeof(mk)), memset((void*)link, 0xff, sizeof(link));
 int u, v, d, e, eofv, top, t, size, res(0);
 for(int i=1; i<=nv; i++){
  if(first[i]==-1) break;
  pre[i]=-1;//here: contruct new tree
  for(queue[top=size=0]=i; top<=size&&link[i]==-1; top++){//for X’s part don’t having counter-part
   for(u=queue[top], eofv=first[u]; eofv!=-1&&link[i]==-1; eofv=es[eofv].next){
    if(mk[es[eofv].j]!=i){//not i’s current tree
     mk[es[eofv].j]=i, queue[++size]=link[es[eofv].j];//back to X set
     if(link[es[eofv].j]!=-1){
      pre[link[es[eofv].j]]=u; continue;//for link to X set’s tree construction
     }
     for(d=u, e=es[eofv].j; d!=-1; t=link[d], link[d]=e, link[e]=d,/*modify pre and fol*/e=t, d=pre[d]);
    }
   }
  }
  if(link[i]!=-1) res++;
 }
 cout<<res<<endl;
 for(int i=1; i<=nv; i++){
  if(first[i]==-1) break;
  if(link[i]!=-1) cout<<link[i]<<" "<<i<<endl;
 } 
}
 
3,Hopcroft-Karp算法
  • DFS版本.严格按照算法艺术的描述实现之:先用BFS做m步来进行最短路标定[HK_BFS里面的逻辑],把未盖点的距离标号为0放入队列,每次从队列中取出元素u(它一定是X中的结点)并把u中所有没标号的邻居v标上号d(v)=d(u)+1。如果v是匹配点,则设置d(pair(v))=d(v)+1并把pair(v)放到队列。pair(v)也是X结点。[这个是HK_DFS里面的逻辑].
void Hopcroft_KarpDFS(){//主程序逻辑
 int res(0);
 memset((void*)link, 0xff, sizeof(link));
 while(HK_bfs()){
  for(int i=1; i<=nv; i++){
   if(first[i]==-1) break;
   if(link[i]==-1&&HK_dfs(i)) ++res;
  }
 }
 cout<<res<<endl;
 for(int i=1; i<=nv; i++){
  if(first[i]==-1) break;
  if(link[i]!=-1) cout<<link[i]<<" "<<i<<endl;
 }
}
 
bool HK_bfs(){
 bool found=false;
 int top=0, size=0;
 for(int i=1; i<=nv; i++){
  if(link[i]==-1) queue[size++]=i;
  dist[i]=0;//all distance pointers reset for preparation of dist[1…nv]
 }
 for(; top<size; top++){
  int x=queue[top];
  for(int eofv=first[x]; eofv!=-1; eofv=es[eofv].next){
   if(!dist[es[eofv].j]){//another side is 0
    dist[es[eofv].j]=dist[x]+1;
    if(link[es[eofv].j]==-1) found=true;
    else dist[link[es[eofv].j]]=dist[es[eofv].j]+1,
     queue[size++]=link[es[eofv].j];//change current link
   }
  }//for
 }//for
 return found;
}
 
bool HK_dfs(int u){
 for(int e=first[u]; e!=-1; e=es[e].next){
  if(dist[es[e].j]==dist[u]+1){//hehe!
   dist[es[e].j]=0;
   if(link[es[e].j]==-1||HK_dfs(es[e].j)){
    link[u]=es[e].j, link[es[e].j]=u; return true;
   }
  }
 }
 return false;
}
 
  • BFS版本:在浙大网站上发现的,可惜有个地方src没看得很懂,而且MS程序逻辑中有些问题[瞎说的],放在上面吧!
void Hopcroft_KarpBFS(){
 int i , u , t , d , e, eofv , top , size , res(0) , p , flag;
 memset((void*)mk, 0xff, sizeof(mk)), memset((void*)link, 0xff, sizeof(link));
 for(p=1, flag=1; flag; p++){//if
  flag=0;
  for(top=size=0, i=1; i<=nv; i++){
   if(first[i]==-1) break;
   if(link[i]==-1) queue[++size]=i, pre[i]=-1, src[i]=i;
  }
  for(;top<=size;top++){//poo-up for queue
   u=queue[top];
   if(link[src[u]]!=-1) continue;//if src[u] have already has the following child
   for(eofv=first[u]; eofv!=-1; eofv=es[eofv].next){
    if(mk[es[eofv].j]!=p){//not the current branches, yeah
     mk[es[eofv].j]=p, queue[++size]=link[es[eofv].j];
     if(link[es[eofv].j]!=-1){
      pre[link[es[eofv].j]]=u, src[queue[size]]=src[u] ; continue ;
     }
     for(size–,flag=1,d=u,e=es[eofv].j; d!=-1;t=link[d], link[d]=e,link[e]=d ,e=t ,d=pre[d]) ;
    }
   }
  }
 } 
 for(int i=1; i<=nv; i++){
  if(first[i]==-1) break;
  res++;
 }
 cout<<res<<endl;
 for(int i=1; i<=nv; i++){
  if(first[i]==-1) break;
  if(link[i]!=-1) cout<<link[i]<<" "<<i<<endl;
 } 
}
作为常识HK算法还是比较高效的,呵呵!
 
3.二分图的Konig定理:最大匹配数和最小覆盖数一样大的.进一步的,最大独立集和最小覆盖集互为补集,那么|N|-最大匹配数=最大独立集.
4.二分图的最优带权匹配[KM算法]
昨晚看得我头晕脑胀的,其实K.M.是提出了一个数学的构造方式,<实用>上的算法点评的很清楚:KM算法在寻找可增广路的过程中,反复修改顶标,直到找到一条增广路为止.好了,切入正题.
测试数据:
5 5
5 1 3 2 5 3 5 4 4 5 1//前向星表示:x1->y1…yn value
4 1 2 2 2 4 2 5 2
4 1 2 2 4 3 4 4 1
2 2 1 3 1
5 1 1 2 2 3 1 4 3 5 3
 
KM基本算法框架:[基于基本匈牙利算法DFS的框架],此外百度空间有个讲解,写的不错,引用在这里[百度词条]
for i->x1 to xn{
       //将Gl中值置空
       while(!find(i)){//若不能找到增广路可达,目标:每个X集都有项匹配
             adjust();//调整顶标,策略:从X集到可达Y集找出最小的调整量;更新其lx[1…nx],ry[1…ny]顶标
             //将Gl中值置空
       }
}
 
实现程序代码:
#include <stdlib.h>
#include <assert.h>
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=10, MAXE=200;
typedef struct Edge{
 int i, j, w, next;
}Edge;
Edge es[MAXE];
int eid, firstX[MAXN],/*just for X set*/lx[MAXN], ry[MAXN], linkY[MAXN], nx, ny;
bool l[MAXN], r[MAXN];//for Gl
//declaration
void createGraph();
void clr();
void addEdge(int i, int j, int w);
void KM();
bool find(int s);
void adjust();
//implementation
void createGraph(){
 ifstream in("input.txt");
 if(!in) exit(EXIT_FAILURE);
 cin.rdbuf(in.rdbuf());
 cin>>nx>>ny;clr();
 int m, e, w;
 for(int i=1; i<=nx; i++){
  cin>>m;
  for(int j=1; j<=m; j++) cin>>e, cin>>w, addEdge(i, e, w);
 }
}
void clr(){//很容易写错的地方
 eid=0, memset((void*)firstX, 0xff, sizeof(firstX)), memset((void*)linkY, 0xff, sizeof(linkY));//linkY is not the current Set
}
void addEdge(int i, int j, int w){
 es[eid].i=i, es[eid].j=j, es[eid].w=w;
 es[eid].next=firstX[i], firstX[i]=eid; eid++;
}
//KM algorithm
void KM(){
 int maxx=0;
 for(int i=1; i<=nx; i++){
  maxx=0;
  for(int e=firstX[i]; e!=-1; e=es[e].next){
   if(es[e].w>maxx) maxx=es[e].w;
  }
  lx[i]=maxx;//for find the max of each vertex
 }
 memset((void*)ry, 0, sizeof(ry));
 for(int i=1; i<=nx; i++){
  memset((void*)l, 0, sizeof(l)), memset((void*)r, 0, sizeof(r));
  while(!find(i)){
   adjust();  
   memset((void*)l, 0, sizeof(l)), memset((void*)r, 0, sizeof(r));
  }
 }
 int res(0);
 for(int i=1; i<=ny; i++)
  if(linkY[i]!=-1) res++;
 cout<<res<<endl;
 for(int i=1; i<=ny; i++){
  if(linkY[i]!=-1) cout<<linkY[i]<<" "<<i<<endl;
 }
}
//bool find
bool find(int u){
 l[u]=true;
 for(int e=firstX[u]; e!=-1; e=es[e].next){
  if(!r[es[e].j]&&lx[u]+ry[es[e].j]==es[e].w){
   r[es[e].j]=true;//here:forget
   if(linkY[es[e].j]==-1||find(linkY[es[e].j])){
    linkY[es[e].j]=u; return true;
   }
  }
 }
 return false;
}
//void adjust
void adjust(){
 int minxx=INT_MAX;
 for(int i=1; i<=nx; i++){//in Gl
  if(l[i]){
   for(int e=firstX[i]; e!=-1; e=es[e].next){
    if(!r[es[e].j])
     minxx=min(minxx, lx[i]+ry[es[e].j]-es[e].w);
   }
  }
 }
 assert(minxx!=INT_MAX);
 for(int i=1; i<=nx; i++){//dummy implementation here!
  if(l[i]) lx[i]-=minxx;
 }
 for(int i=1; i<=ny; i++){//dummy implementation here!
  if(r[i]) ry[i]+=minxx;
 }
}
int _tmain(int argc, _TCHAR* argv[])
{
 createGraph();
 KM();
 return 0;
}
Advertisements