预计阅读时间：10分钟

一、简介

二分图の定义

        二分图又叫二部图，是图论中的一种特殊模型。

        假设S=(V,E)是一个无向图。如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，就可以称图S为一个二分图。简单来说，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

二分图の匹配

        给定一个二分图S，在S的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

        极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。

        最大匹配是所有极大匹配当中边数最大的一个匹配。

        选择这样的边数最大的子集称为图的最大匹配问题。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
        完全匹配一定是极大匹配，但是极大匹配不一定是完全匹配。下图就是一个最大匹配。

 二分图の判断

       对于二分图的判断方法最常见的是染色法，就是对每一个点进行染色操作，只用黑白两种颜色，能不能使所有的点都染上了色且相邻两个点的颜色不同？如果可以那么这个图就是一个二分图，对于判断是否是一个二分图的方法可以用dfs和bfs两种方式去实现。代码参见“代码实现”部分。

二分图の最大匹配

        给定一个二分图S，在S的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

        首先要了解两个概念：

|交替路|从一个未匹配的点出发，依次经过未匹配边、匹配边、未匹配边....

|增广路|从一个未匹配的点出发，走交替路，到达了一个未匹配过的点。  

        对于求二分图最大匹配的算法可以用网络流去跑一个最大流求解，还可以用二分图的常见算法匈牙利算法，这个算法的核心就是去找未匹配的点，然后从这个点出发去寻找增广路，因为增广路有几个主要的特点：

• 增广路有奇数条边 。
• 路径上的点一定是一个在X边，一个在Y边，交错出现。
• 起点和终点都是目前还没有配对的点。
• 未匹配边的数量比匹配边的数量多1。

        重点是第4点，我们可以根据此特性，把这条增广路中的匹配边改为未匹配边，把未匹配边改为匹配边，这样我们就可以使总匹配边数+1了，根据上面的图得出下图，很显然匹配边多了一条。

        代码见“代码实现”部分。

二、代码实现

“二分图の判断”配套代码：

BFS判断二分图

vectorG[maxn];//存边
int col[maxn];//标记顶点颜色
int n,m;//点和边的个数
bool bfs()
{queueq;q.push(1);//放入第一个点memset(col,0,sizeof(col));col[1]=1;//先标记第一个点为1while(!q.empty()){int v=q.front();q.pop();for(int i=0; i

---

“二分图の最大匹配”配套代码

匈牙利算法代码

vector G[maxn];//存边
int pre[maxn];//记录匹配点
bool vis[maxn];//标记是否匹配过
int n,m;//n个点 m条边
bool dfs(int x)
{for(int i=0; i