二分图最大匹配-匈牙利算法

二分图最大匹配-匈牙利算法

匈牙利算法是通过找增广路来实现匹配数的增加。当前匹配方案如果再也找不到增广路，则匹配数达到最大。

核心流程：

1. 从任意一个未被匹配的点开始。任选一条边（u-v）开始配对。如果v此时没有被配对，则配对成功。

   如果v已经被配对了（v-w）。那么先尝试对w进行另一个配对，如果w成功匹配另一个点（w-x），那么

   u-v配对成功，我们找到了一条增广路。实际中要用标记数组防止 w-u的情况 ：w和u必然在同一边

   • 实际上。我们只要对二分图的一边进行匹配，一边匹配完了另一边自然也匹配好了。该算法实际上是对一边（例如左边）进行匹配，详情看洛谷例题

2. 如果配对失败那么尝试u的其他配对方案，直到u配对成功或所有方案均尝试为止

3. 继续对剩下的顶点进行配对

4. 输出配对数

示例问题：CP配对

有2n个人物，m组关系，两个人物之间有关系则可以组成cp，求最大匹配数

数据格式：

3 5
1 1
1 2
2 2
2 3
3 1

• 第一行n，m：表示左右两边各n个人，有m组关系
• 接下来m行，每行两个数字u，v：表示左边的u和右边的v可以组成cp

整体代码：

//二分图的最大匹配
#include<iostream>
using namespace std;

int peo, rel;
//人数和关系函数
int num = 0;//保存匹配数
int counter = 0;//执行次数

bool dfs(int*match,bool**e,bool*book,int u)
{
	for (int i = 1; i <= peo; i++)//枚举每一条关系
	{
		if (book[i] == false && e[u][i] == true)//如果i点没被访问且i点和u点有关系
		{
			book[i] = true;//标记i点已经被访问
			//如果i点未找到匹配或者i点的匹配对象找到了新的匹配
			if (match[i] == 0 || dfs(match, e, book, match[i]) == true)
			{

				match[i] = u;//i点和当前点匹配
				return true;
			}
		}
	}

	return false;//否则匹配失败
}

int main()
{
	cin >> peo >> rel;
	int* match = new int[peo + 1];//保存匹配关系的数组
	bool** e = new bool* [peo + 1];//保存图的邻接矩阵
	bool* book = new bool[peo + 1];//标记是否被访问
	//初始化矩阵和匹配数组
	for (int i = 0; i <= peo; i++)
	{
		e[i] = new bool[peo + 1];
		for (int j = 0; j <= peo; j++)
		{
			e[i][j] = false;
		}
		match[i] = 0;
	}
	//录入关系
	int a, b;
	for (int i = 0; i < rel; i++)
	{
		cin >> a >> b;
		e[a][b] = true;
		e[b][a] = true;
	}
	//开始匹配
	for (int i = 1; i <= peo; i++)
	{
		//每次匹配要初始化标记数组
        for (int j = 1; j <= peo; j++)
		{
			book[j] = false;
		}
        //匹配成功要计数
		if (dfs(match,e,book,i))
		{
			num++;
		}
	}

	//输出匹配数
	cout << num;

	delete[] match;
	delete[] book;
	delete[] e;
	return 0;
}

核心代码：

bool dfs(int*match,bool**e,bool*book,int u)
{
	for (int i = 1; i <= peo; i++)//枚举每一条关系
	{
		if (book[i] == false && e[u][i] == true)//如果i点没被访问且i点和u点有关系
		{
			book[i] = true;//标记i点已经被访问
			//如果i点未找到匹配或者i点的匹配对象找到了新的匹配
			if (match[i] == 0 || dfs(match, e, book, match[i]) == true)
			{

				match[i] = u;//i点和当前点匹配
				return true;
			}
		}
	}

	return false;//否则匹配失败
}

//开始匹配
for (int i = 1; i <= peo; i++)
{
	//每次匹配要初始化标记数组
    for (int j = 1; j <= peo; j++)
	{
		book[j] = false;
	}
    //匹配成功要计数
	if (dfs(match,e,book,i))
	{
		num++;
	}
}

洛谷例题：

【模板】二分图最大匹配

题目描述

给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

输入格式

输入的第一行是三个整数，分别代表 $n$，$m$ 和 $e$。

接下来 $e$ 行，每行两个整数 $u, v$，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。

输出格式

输出一行一个整数，代表二分图最大匹配的边数。

样例 #1

样例输入 #1

1 1 1
1 1

样例输出 #1

1

样例 #2

样例输入 #2

4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1

样例输出 #2

2

提示

数据规模与约定

对于全部的测试点，保证：

• $1 \leq n, m \leq 500$。
• $1 \leq e \leq 5 \times 10^4$。
• $1 \leq u \leq n$，$1 \leq v \leq m$。

不保证给出的图没有重边。

AC代码

#include<iostream>
using namespace std;

bool arr[510][510];//图
bool book[510];//标记数组
int match[510];//匹配信息
int lefter, righter, edge;//左边点数，右边点数，边数
int num = 0;//匹配数

bool dfs(int u)
{
	for (int i = 1; i <= righter; i++)
	{
		if (book[i] == false && arr[u][i] == true)
		{
			book[i] = true;
			if (match[i] == 0 || dfs(match[i]) == true)
			{
				match[i] = u;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	cin >> lefter >> righter >> edge;
	int a, b;
	for (int i = 0; i < edge; i++)
	{
		cin >> a >> b;
		arr[a][b] = true;
	}

	for (int i = 1; i <= lefter; i++)
	{
		for (int j = 1; j <= lefter; j++)
		{
			book[j] = false;
		}
		if (dfs(i) == true)
		{
			num++;
		}
	}
	cout << num;
	return 0;
}