二分匹配

PS：二分图匹配这一章的内容，我认为最重要的是要弄清楚概念。

一些定义：

二分图：二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如

果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联

的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个

二分图。记为G=(A,B;E)。

二分图匹配：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

需要强调的是：集合A或者B中，本集合中的元素之间是没有关系的。

最大匹配可用最大流来解，最佳匹配可用最大流最小费用流来解。

二分匹配的意义何在，最大匹配、最佳匹配算法的时间复杂度低。

一、最大匹配

最大匹配是找到匹配数最多的匹配。

DFS版匈牙利算法：代码最简洁。时间复杂度为O(n*m), 空间复杂度为O(n*n)。

不卡时间大家都喜欢用这个。

BFS版匈牙利算法：代码稍多。时间复杂度为O(n*m), 空间复杂度为O(n*n)

Hopcroft-Karp算法：对匈牙利算法进行了优化，时间复杂度O(m√n)。代码很长，空间复杂度为O(m*m)。

需要说明的是：准备模版的时候还是多准备一些比较好，有些题目是卡时间，有些却是卡空间。所以有些题目用好的算法就是AC不了。

DFS匈牙利算法模版：

 1 //适合边比较多的图
 2 const int N=300;
 3 bool bmap[N][N],bmask[N];
 4 int cx[N],cy[N];
 5 int nx,ny,ans;
 6 int findpath(int u)
 7 {
 8     int i,j;
 9     for(i=1;i<=ny;i++)
10     {
11         if(bmap[u][i]&&!bmask[i])
12         {
13             bmask[i]=1;
14             if(cy[i]==-1||findpath(cy[i]))
15             {
16                 cy[i]=u; cx[u]=i;
17                 return 1;
18             }
19         }
20     }
21     return 0;
22 }
23 void maxmatch()
24 {
25     int i ,j;
26     ans=0;
27     for(i=1;i<=nx;i++) cx[i]=-1;
28     for(i=1;i<=ny;i++) cy[i]=-1;
29     for(i=1;i<=nx;i++)
30     {
31         if(cx[i]==-1)
32         {
33             for(j=1;j<=ny;j++)
34                 bmask[j]=0;
35             ans+=findpath(i);
36         }
37     }
38 }
39 void init()
40 {
41     memset(bmap,0,sizeof(bmap));
42 }
43 
44 (2)匈牙利算法BFS    时间复杂度O(n*m)
45 
46 const int N=1010;
47 int bmap[N][N],cx[N],cy[N],bmask[N],que[N],pre[N];
48 int nx,ny,ans;
49 void maxmatch()
50 {
51     ans=0;
52     int qs,qe;
53     memset(cx,-1,sizeof(cx));
54     memset(cy,-1,sizeof(cy));
55     memset(bmask,-1,sizeof(bmask));
56     for(int i=1;i<=nx;i++)
57     {
58         if(cx[i] == -1)
59         {
60             qs=qe=0;
61             que[qe++]=i;
62             pre[i]=-1;
63             bool flag=0;
64             while(qs<qe&&!flag)
65             {
66                 int u=que[qs];
67                 for(int v=1;v<=ny&&!flag;v++)
68                 {
69                     if(bmap[u][v]&&bmask[v]!=i)
70                     {
71                         bmask[v]=i;que[qe++]=cy[v];
72                         if(cy[v]>=0) pre[cy[v]]=u;
73                         else
74                         {
75                             flag=1;
76                             int d=u,e=v;
77                             while(d!=-1)
78                             {
79                                 int t=cx[d];
80                                 cx[d]=e; cy[e]=d;
81                                 d=pre[d]; e=t;
82                             }
83                         }
84                     }
85                 }
86                 qs++;
87             }
88             if(cx[i]!=-1) ans++;
89         }
90     }
91 }
92 void init()
93 {
94     memset(bmap,0,sizeof(bmap));
95 }

View Code

Hopcroft-Karp算法模版：有时候顶点较多，所以直接用邻接表，没用邻接矩阵。

 1 const int N=10150,INF=0x3f3f3f3f;
 2 int cx[N],cy[N],dx[N],dy[N];
 3 bool bmask[N];
 4 int nx,ny,dis,ans;
 5 vector<int> bmap[N];
 6 bool searchpath()
 7 {
 8     queue<int> q;
 9     dis=INF;
10     memset(dx,-1,sizeof(dx));
11     memset(dy,-1,sizeof(dy));
12     for(int i=1;i<=nx;i++)
13     {
14         if(cx[i]==-1){ q.push(i); dx[i]=0; }
15         while(!q.empty())
16         {
17             int u=q.front(); q.pop();
18             if(dx[u]>dis) break;
19             for(int i=0;i<bmap[u].size();i++)
20             {
21                 int v=bmap[u][i];
22                 if(dy[v]==-1)
23                 {
24                     dy[v]= dx[u] + 1;
25                     if(cy[v]==-1) dis=dy[v];
26                     else
27                     {
28                         dx[cy[v]]= dy[v]+1;
29                         q.push(cy[v]);
30                     }
31                 }
32             }
33         }
34     }
35     return dis!=INF;
36 }
37 int findpath(int u)
38 {
39     for(int i=0;i<bmap[u].size();i++)
40     {
41         int v=bmap[u][i];
42         if(!bmask[v]&&dy[v]==dx[u]+1)
43         {
44             bmask[v]=1;
45             if(cy[v]!=-1&&dy[v]==dis) continue;
46             if(cy[v]==-1||findpath(cy[v]))
47             {
48                 cy[v]=u; cx[u]=v;
49                 return 1;
50             }
51         }
52     }
53     return 0;
54 }
55 void maxmatch()
56 {
57     ans=0;
58     memset(cx,-1,sizeof(cx));
59     memset(cy,-1,sizeof(cy));
60     while(searchpath())
61     {
62         memset(bmask,0,sizeof(bmask));
63         for(int i=1;i<=nx;i++)
64             if(cx[i]==-1) ans+=findpath(i);
65     }
66 }
67 void init()
68 {
69     for(int i=0;i<N;i++) bmap[i].clear();
70 }

View Code

题目类型：

1、判断是否构成二分图 http://www.cnblogs.com/Potato-lover/p/3985869.html

2、二分 + 最大匹配 http://www.cnblogs.com/Potato-lover/p/3989675.html

3、奇偶建图 http://www.cnblogs.com/Potato-lover/p/3991533.html

二、最佳匹配

与最大匹配不同的是，最佳匹配是在每一个匹配之间加一个权值。求的就是权值之和最大的匹配。

Kuhn Munkras 算法：时间复杂度为O(m*m*n)。

模版：

 1 const int N=110, INF=0x3f3f3f3f;
 2 int Map[N][N],mat1[N],mat2[N];
 3 int KM(int m,int n)
 4 {
 5     int s[N],t[N],a[N],b[N];
 6     int i,j,k,p,q,ans=0;
 7     for(i=0;i<m;i++)
 8     {
 9         a[i]=-INF;
10         for(j=0;j<n;j++)
11             a[i]=Map[i][j]>a[i]?Map[i][j]:a[i];
12         if(a[i]==-INF) return -1;//cannot match
13     }
14     memset(b,0,sizeof(b));
15     memset(mat1,-1,sizeof(mat1));
16     memset(mat2,-1,sizeof(mat2));
17     for(i=0;i<m;i++)
18     {
19         memset(t,-1,sizeof(t));
20         p=q=0;
21         for(s[0]=i;p<=q&&mat1[i]<0;p++)
22         {
23             for(k=s[p],j=0;j<n&&mat1[i]<0;j++)
24             {
25                 if(a[k]+b[j]==Map[k][j]&&t[j]<0)
26                 {
27                     s[++q]=mat2[j]; t[j]=k;
28                     if(s[q]<0)
29                         for(p=j;p>=0;j=p)
30                         {
31                             mat2[j]=k=t[j];p=mat1[k]; mat1[k]=j;
32                         }
33                 }
34             }
35         }
36         if(mat1[i]<0)
37         {
38             i--,p=INF;
39             for(k=0;k<=q;k++)
40             {
41                 for(j=0;j<n;j++)
42                     if(t[j]<0&&a[s[k]]+b[j]-Map[s[k]][j]<p)
43                         p=a[s[k]]+b[j]-Map[s[k]][j];
44             }
45             for(j=0;j<n;j++) b[j]+=t[j]<0?0:p;
46             for(k=0;k<=q;k++) a[s[k]]-=p;
47         }
48 }
49     for(i=0;i<m;i++) ans+=Map[i][mat1[i]];
50     return ans;
51 }
52 void init()
53 {
54     for(int i=0;i<N;i++)
55         for(int j=0;j<N;j++)
56              Map[i][j]=-INF;
57 }

View Code

题目：

http://www.cnblogs.com/Potato-lover/category/615224.html

三、多重匹配

最大匹配值允许A集合与B集合是一一对应。多重匹配可以使得B的元素与多个A的元素匹配。

算法模版：

 1 const int N=1010;
 2 int cy[N][N],vcy[N];
 3 bool bmask[N],bmap[N][N];
 4 int nx,ny,limit,L,R;
 5 bool findpath(int u)
 6 {
 7     int i,j;
 8     for(i=1;i<=ny;i++)
 9     {
10         if(bmap[u][i]&&!bmask[i])
11         {
12             bmask[i]=1;
13             if(vcy[i]<limit)
14             {
15                 cy[i][++vcy[i]] =u;
16                 return 1;
17             }
18             for(j=1;j<=vcy[i];j++)
19             {
20                 if(findpath(cy[i][j]))
21                 {
22                     cy[i][j]=u;
23                     return 1;
24                 }
25             }
26         }
27     }
28     return 0;
29 }
30 bool mulmatch()
31 {
32     memset(vcy,0,sizeof(vcy));
33     for(int i=1;i<=nx;i++)
34     {
35         memset(bmask,0,sizeof(bmask));
36         if(!findpath(i)) return 0;
37     }
38     return 1;
39 }
40 void init()
41 {
42     memset(bmap,0,sizeof(bmap));
43 }
44 int main()
45 {
46     L=0,R=nx;
47     while(L<=R)
48     {
49         limit=(L+R)/2;
50         if(mulmatch()) R=limit-1;
51         else L=limit+1;
52     }
53     printf("%d
",L);
54 }

View Code

题目：

2289 Jamie's Contact Groups

四、二分图模型的应用

1、二分图最小点覆盖 http://www.cnblogs.com/Potato-lover/p/3980411.html

2、有向无环图的最小路径覆盖 http://www.cnblogs.com/Potato-lover/p/3989625.html

3、二分图的最大独立集 http://www.cnblogs.com/Potato-lover/p/3980491.html