二分图匹配

迷南。 2022-12-19 03:38 158阅读 0赞

**Bi-partite graph**

![20130902222653718][]

二分图的定义：  
二分图是这样的一个图，它的顶点可以分为两个集合X和Y。所有的边关联的两个顶点中，恰好一个属于集合X，一个属于集合Y。

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

增广路：

从未盖点开始经过非匹配边、匹配边、非匹配边……序列，最终通过一条非匹配边到达另一个未盖点

特点： 非匹配边个数比匹配边个数多一  
 如果把匹配边和非匹配边互换…

![20130902223503015][]

上图为一条增广路，黑色边为匹配边，如果把匹配边和非匹配边互换：

![20130902223405968][]

增广路定理：

匹配是最大匹配当且仅当不存在增广路

这个定理适用于任意图

![20130902223929562][]

**二分图的最大匹配**

定义：  
图中包含边数最多的匹配称为图的最大匹配。

![20130902222804984][]

如图所示：蓝色部分就构成一个最大匹配，同时它也是一个完美匹配

完美匹配：

如果所有点都在匹配边上，称这个最大匹配是完美匹配。

**匈牙利算法（时间复杂度O(nm)）**

其思想是用宽度优先搜索来找增广路径（和floodfill算法类似  
转化为单位容量简单网络的最大流问题  
在二分图的基础上，加入源点s和汇点t，让s与每个X结点连一条边，每个Y结点和t连一条边，所有弧的容量为1。这样，饱和弧就对应着匹配边。

匈牙利算法：  
寻找增广路：  
初始时最大匹配为空

for 二分图左半边的每个点i

do 从点i出发寻找增广路径  
如果找到，则把它取反（即增加了总了匹配数）。  
  
  
复杂度：

时间复杂度 [邻接矩阵][Link 1]：最坏为O(n^3） [邻接表][Link 2]：O(mn)

空间复杂度 邻接矩阵：O(n^2） 邻接表：O(m+n)

//邻接矩阵-C++
    #include<iostream>
    #include<cstring>
    using namespace std;
    int map[105][105]; //邻接矩阵 
    int visit[105]; //记录Y中的每个点是否被搜索过
    int flag[105];//记录Y中的点匹配的点的编号
    int n,m;
    bool dfs(int a)
    {
    	for(int i=1;i<=m;i++)
    	{
    		if(map[a][i] && !visit[i]) //如果节点i与a相邻 并且 未被查找过
    		{
    			visit[i]=1; //标记i为已查找过
    			
    			if(flag[i]==0  //如果i未在前一个匹配M中
    			|| dfs(flag[i]))   //i在匹配M中，但是从与i相邻的节点出发可以有增广路
    			{
    				flag[i] = a;//记录查找成功记录
    				return true;  //返回查找成功
    			}
    		}
    	}
    	return false;
    }
    int main()
    {
    	while(cin>>n>>m)
    	{
    		memset(map,0,sizeof(map));
    		for(int i=1;i<=m;i++)
    		{
    			int x,y;
    			cin>>x>>y;
    			map[x][y]=1;
    		}
    		memset(flag,0,sizeof(flag));
    		int result=0;
    		for(int i=1;i<=n;i++)
    		{
    			memset(visit,0,sizeof(visit));   //清空上次搜索时的标记
    			if(dfs(i)) //从节点i尝试扩展
    			result++;
    		}
    		cout<<result<<endl;
    	}
    	return 0;
    }

看一道例题：PKU 1469

[20130902222653718]: /images/20221120/9a1702bd06044b33a7f8993cf117585c.png
[20130902223503015]: /images/20221120/89bb3161f7754ebfbed4400ecb552cb1.png
[20130902223405968]: https://img-blog.csdn.net/20130902223405968
[20130902223929562]: https://img-blog.csdn.net/20130902223929562
[20130902222804984]: https://img-blog.csdn.net/20130902222804984
[Link 1]: http://baike.baidu.com/view/549589.htm
[Link 2]: http://baike.baidu.com/view/549594.htm