ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

---

---

一、前言

二分图定义：

二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

二分图的匹配：

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

二分图的最大匹配：

所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

补充概念

完美匹配：

如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

推荐大家几个学图论的工具

数据结构和算法可视化工具
图形编译器

---

二、匈牙利算法的实现

推荐图的存储与遍历

存图，采用邻接表来存稀疏图

//邻接表写法，存稀疏图
int h[N],ne[N],e[N],idx;

void add(int a , int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void init()
{
    memset(h,-1,sizeof h);
}
//存边只存一边就行了，虽然是无向图。
for(int i = 0 ; i < n ; i ++)
{
    int a,b;
    cin>>a>>b;
    add(a,b);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

算法模板

//match[j]=a,表示点j现在与a点匹配
int match[N];
//st[]数组我称为临时预定数组，st[j]=a表示一轮模拟匹配中，点j与点a匹配了。
int st[N];

//这个函数的作用是用来判断,如果加入x来参与匹配,会不会使匹配数增多
int find(int x)
{
    //遍历点x连接的点
    for(int i = h[x] ; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个点尚未被预定
        {
            st[j] = true;//那x就预定这个点
            //如果点j没有匹配点，或者她原来的点能够预定其它点。配对成功,更新match
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
    return false;
}

//记录最大匹配
int res = 0;
for(int i = 1; i <= n1 ;i ++)
{  
    //因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
    memset(st,false,sizeof st);
    if(find(i)) 
        res++;
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

【模板】二分图最大匹配

【模板】二分图最大匹配

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

1 1 1
1 1
1
2

样例输出 #1

1
1

样例 #2

样例输入 #2

4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1
1
2
3
4
5
6
7
8

样例输出 #2

2
1

提示

数据规模与约定

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

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

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

AC代码

#include 
#include 
using namespace std;

const int N=510,M=1e5+7;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];

void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void init()
{
	memset(h,-1,sizeof h);
}

int find(int x)
{
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(!st[j])
		{
			st[j]=true;
			if(!match[j]||find(match[j]))
			{
				match[j]=x;
				return true;
			}
		}
	}
	return false;
}



int main()
{
	init();
	cin>>n1>>n2>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	int res=0;
	
	for(int i=1;i<=n1;i++)
	{
		memset(st,false,sizeof st);
		if(find(i))
		res++;
	}
	cout<<res<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

---

最后