二分图
先介绍一下什么是二分图，二分图也叫二部图，设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图，如下图所有的顶点可以分成A，B两个集合，而A集合与B集合中的点与自己的阵营的点是没有连线的（A集合的点只与B集合的点有边相连），则称这个为一个二分图
而二分图的最大匹配的含义，就是说在这A，B两个集合中不断选择两个存在连线（只有存在连线才能连起来，而且每个点只能匹配一次）的两个点相连，求最多可以有多少条连线即这个二分图的最大匹配数，对于上面这张图我们用红线来演示一下，第一次选择A1和B1相连，第二次选择A2和B2相连，第三次发现与A3相连的B1与B2都已经被选择了，那么我们需要尝试给匹配过的点换一个点，看看能不能腾出一个位置给A3，我们先尝试给A1换一个点，A1还可以与B2相连，但是B2同样被A2占用，则我们考虑给A2也换一个点，这样A1就能换上A2原本的占的B2，而就能将B1腾出来给A3了（这很像是一个递归的过程，递归腾位置），黄线代表除去的原来的匹配方式，而对于A4我们无论如何都无法修改之前的匹配方式而使得总匹配数量增加，所以这个二分图的最大匹配就是3
而对于一个点来说，判断从它出发能否在另一个集合中找到一个顶点使得整张图的总匹配数增加的过程实际上可以理解为一个找寻增广路的过程（增广路不是网络流的概念吗？！别着急，听我简单给你解释一下）对于上图的第二张图，我们要开始给A3找匹配点的时候，发现B1，B2都被占用，则开始寻找所谓的增广路，能找到一条增广路就能使总匹配数+1，而找增广路的要旨就是：从A集合中的一个点出发，我们能不断在两个集合中找到一个未匹配过的顶点，前提是且他们之间有连线，且满足连线的过程是，这条边未匹配过，匹配过，未匹配过，匹配过，未匹配过...（总之边的数量是奇数，且两头都是未匹配过）,如下图的模拟：从A3出发，A3->B1->A1->B2->A2->B3，边的颜色为蓝（未匹配），红（匹配），蓝（未匹配），红（匹配），蓝（未匹配），满足上面说的找增广路的要求（而最后的B3->A4虽然也有一条蓝色连线但是此时需要红色的才能继续连下去故不选择），一旦我们找到了增广路，我们只要将红蓝颜色的连线反转，就能得到一种总匹配数+1的匹配方式，也就是下面的第二张图的匹配方式（黄色线就是未匹配的意思，这是它是拆出来的，之前为红色）
那么对于A4这个点来说，我们因为B3已经被占用了，则我们依旧尝试取找寻增广路，从A4->B3->A2->B2->A1->B1->A3，到此为止无法继续走下去，而边的颜色为蓝（未匹配），红（匹配），蓝（未匹配），红（匹配），蓝（未匹配），红（匹配），总数为偶数，不满足开头结尾为未匹配边，则无法找到增广路，此时所有A集合中的顶点用完，二分图的最大匹配数为3
当然上述用增广路的概念来解释这个原理是辅助我们理解这个二分图的，而关于匈牙利算法的使用，它的计算过程是每一次从A集合中取一个点，将其于B集合中有连线的点依次对照，如果可以相连则将这两个点连起来，遍历下一个A集合的点，如果有连线却已经被A集合中上面的点占去了，则尝试给占去这个Bj的点的Ai换一个有连线未被占用的点，如果又被占了则再考虑把占用的换一个，是一个递归的过程（一开始的三张图我们已经推过一边了，重点就是让别人给自己腾位置）
关于具体的讲解代码我们通过一题二分图最大匹配的模板题 HDU2063来解析
题目描述
RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？
输入
输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
输出
对于每组数据，输出一个整数，表示可以坐上过山车的最多组合数。
样例输入
6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0
样例输出
3
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 using namespace std; 5 6 const int N = 505; 7 int mat[N][N]; 8 int boy[N]; //记录男孩i被女孩选择的女孩编号，未被选则0 9 int vis[N]; //很巧妙的使用，每次记录男孩i是否被占用了 10 int k, m, n; 11 12 bool dfs(int x){ 13 for(int i = 1; i <= n; i++){ //遍历所有的男生编号 14 if(mat[x][i] == 1 && vis[i] == 0){ //如果有连线且boy[i]没有被本次查找遍历过 15 vis[i] = 1; //假设i号boy被遍历到了 16 if(boy[i] == 0 || dfs(boy[i])){ //如果boy[i]没有被占用或者能把占用boy[i]的人换一个连线，短路原则如果没有被占用则不会执行后面的部分 17 boy[i] = x; //这一步的作用是执意要将boy[i]匹配给x(尽可能给腾位置出来，因为她可能占了别的女生相匹配的男生) 18 return true; 19 } 20 } 21 } 22 return false; 23 } 24 25 int main(){ 26 while(scanf("%d", &k) != EOF){ 27 if(k == 0) break; 28 scanf("%d%d", &m, &n); 29 memset(mat, 0, sizeof(mat)); 30 memset(boy, 0, sizeof(boy)); //boy[]数组存放的是已经匹配好的方案，如果是0则未匹配 31 for(int i = 1; i <= k; i++){ 32 int x, y; 33 scanf("%d%d", &x, &y); 34 mat[x][y] = 1; 35 } 36 int ans = 0; 37 for(int i = 1; i <= m; i++){ 38 memset(vis, 0, sizeof(vis)); //vis每一次都将所有的男生编号都标记为没遍历过，注意区分vis[]和boy[]数组功能的区别 39 if(dfs(i)) ans++; //如果能直接相连或别人腾出位置总数+1 40 } 41 printf("%dn", ans); 42 } 43 return 0; 44 } 45
- 还没有人评论，欢迎说说您的想法！
客服
