[ 图 论 ]二分图判定及其匹配（基础+提高）

在解决判定和匹配任务之前，我想我们应该先了解什么是二分图

定义

二分图，又称二部图，英文名叫 Bipartite graph。

二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。

换言之，存在一种方案，将节点划分成满足以上性质的两个集合。 $-(OIWiki)$

那么首先我们先看一个一般的图

上图用了$6$个点，$6$条边。这样看起来没什么特别的对吧，我们将他做一下调整。

此图和上边的是等价的，但是我们将他们分成了两个集合$A,B$，并且每个集合内部都没有边相连，这种图就是二分图。

了解了什么是二分图，我想我们可以开始我们要讲的判定了，现在你可以动手画一画，是不是所有的图都是二分图呢？显然这是不可能的，但这其中又有什么关系吗？比如现在我给出这样一个图👇

你能将他分成二分图吗？

当我们做这件事的时候，会发现无论怎么分，点$5$必然会和$0$或$1$在一个集合中，为什么？因为图中存在奇数环，这时候我们得出了第一个结论：$当图中有奇数环时，他一定不是二分图,反之没有奇数环的图一定是二分图$

我们多举一个例子：

图中存在长度为$4和8$的环，我们现在将他变成二分图

这是非常容易办到的（

接下来我们介绍如何去判定一个图是不是二分图。我这里给出的是一个常用的算法 $染色法判断二分图$

原理：我们可以将两个集合中的点给一个颜色，例如：$A$集合中的点我们都染成红色，$B$集合中的点我们都染成黑色，我们开一个$color[]$数组来记录每个点的颜色，起始，我们遍历每个点，如果没有被染色，我们就将他染成红色，然后将与他直接相连的点全部染成黑色，同理当我们将这个点染成黑色后，我们就要将与他直接相连的所有点染成红色，在这期间如果染色失败，那么就不是二分图，什么时候会出现染色失败呢？当我们染完一个点后，在染他的所有相邻的点的时候发现有一个点的颜色和他相同，也就是下面图中的情况.

$1$号点发现他的相邻点$0$号点也是红色，那么这样就不行了对吧，就算我们把$1$号点染成黑色，那么也会发现他的相邻点$5$也是黑色，这时候就只能宣布：染色失败，图不是二分图

例题：染色法判定二分图

给定一个 $n$ 个点 $m$ 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示点 $u$ 和点 $v$ 之间存在一条边。

输出格式

如果给定图是二分图，则输出 $Yes$，否则输出 $No$。

数据范围

$1\le n,m\le 10^5$

输入样例：

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

输出样例：

Yes
1

这个题是染色算法的板子题,下面给出完整代码：

#include 
using namespace std;
//------邻接表存边
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int color[N];
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
//-------
//-------染色法判断二分图
bool dfs(int u,int c)
{
	color[u]=c;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(!color[j])//相邻点没有颜色，就染成不同的颜色
		{
			if(!dfs(j,3-c))return false;
		}else if(color[j]==color[u])return false;//相邻点与本身的颜色相同
	}
	return true;//将相邻点全部染色成功，只能说明这个点与他的相邻点没有产生矛盾
}
//--------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//----读入无向边
	memset(h,-1,sizeof h);
	int n,m;cin>>n>>m;
	while(m--)
	{
		int a,b;cin>>a>>b;
		add(a,b);add(b,a);
	}
	//-----
	bool f=true;
	for(int i=1;i<=n;i++)//开始染色
	{
		if(!color[i])
		{
			if(!dfs(i,1))f=false;//如果有一个点染色失败，就宣布失败
		}
	}
	if(f)cout<<"Yes";else cout<<"No";
	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

到这里，我相信你已经对如何判定一个图是不是二分图有所了解了，那么这是远远不够的，因为二分博大精深（

我们将学习下一个知识点：二分图的最大匹配

这里我们不引入所谓的增广路概念，他对我来说比较抽象$hh$，所以我们直接用白话的意思翻译一下，什么是最大匹配

​ _{转载知乎@青烟}

他的最大匹配数就是$3$,因为有三对点完成了匹配,分别是： { x 1 , y 4 } , { x 2 , y 2 } , { x 3 , y 3 } \{x_1,y_4\},\{x_2,y_2\},\{x_3,y_3\} {x1​,y4​},{x2​,y2​},{x3​,y3​}

所以最大匹配数就是一个二分图中，从两个集合中各拿出一个点，组成一对的最大对数。

了解了概念，我们如何求呢？这里给大家介绍一种算法：匈牙利算法

我们用一个例题来说明：二分图的最大匹配

给定一个二分图，其中左半部包含 $n_1$ 个点（编号 $1\sim n_1$），右半部包含 $n_2$ 个点（编号 $1\sim n_2$），二分图共包含 $m$ 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

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

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

输入格式

第一行包含三个整数 $n_1、n_2和m$。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v$，表示左半部点集中的点 $u$ 和右半部点集中的点 $v$ 之间存在一条边。

输出格式

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

数据范围

$1\le n_1,n_2\le 500$
$1\le u\le n1,$
$1\le v\le n2,$
$1\le m\le 10^5$

输入样例：

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

输出样例：

2
1

#include 
using namespace std;
//-------读入边
const int N=510,M=1e5+10;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
//---------

//--------匈牙利算法
bool st[N];
int match[N];
bool find(int u)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(st[j])continue;
		st[j]=true;//我们现占下这个匹配者
		if(!match[j]||find(match[j]))
		//如果右边的点 j 还没有匹配,或者他的匹配者可以换一个（
		{
			match[j]=u;
			return true;
		}
	}
	return false;
}
//--------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//---读边
	memset(h,-1,sizeof h);
	int n1,n2,m;cin>>n1>>n2>>m;
	while(m--)
	{
		int a,b;cin>>a>>b;
		add(a,b);
	}
	//----
	int num=0;
	for(int i=1;i<=n1;i++)//从左边集合开始匹配右边
	{
		memset(st,0,sizeof st);
		if(find(i))num++;
	}
	cout<<num;//输出匹配数量
	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

到此，我们二分图最基础的两个操作已经介绍完了，接下来我们来进行提高部分，我会用题目来进行一些知识点的介绍。

1、染色法+二分 关押罪犯

$S$ 城现有两座监狱，一共关押着 $N$ 名罪犯，编号分别为 $1\sim N$。

他们之间的关系自然也极不和谐。

很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。

我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。

如果两名怨气值为 $c$ 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 $c$ 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 $S$ 城 $Z$ 市长那里。

公务繁忙的 $Z$ 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 $N$ 名罪犯间的矛盾关系后，警察局长觉得压力巨大。

他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。

假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 $Z$ 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入格式

第一行为两个正整数 $N$ 和 $M$，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的 $M$ 行每行为三个正整数 $a_j，b_j，c_j$，表示 $a_j$ 号和 $b_j$ 号罪犯之间存在仇恨，其怨气值为 $c_j$。

数据保证$1\le a_j<b_j<N,0<c_j\le 10^9$ 且每对罪犯组合只出现一次。

输出格式

输出共 $1$ 行，为 $Z$ 市长看到的那个冲突事件的影响力。

如果本年内监狱中未发生任何冲突事件，请输出 $0$。

数据范围

$N\le 20000,M\le 100000$

输入样例：

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
1
2
3
4
5
6
7

输出样例：

3512
1

时间复杂度： $O((N+M)logC)$
将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。
那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。

我们在$[0,10^9]$ 之间枚举最大边权 $limit$，当 $limit$ 固定之后，剩下的问题就是：

判断能否将所有点分成两组，使得所有权值大于$limit$ 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 $limit$ 的边构成的新图是否是二分图。
判断二分图可以用染色法，时间复杂度是$O(N+M)$，其中 $N$ 是点数，$M$ 是边数 — yxc

#include 
using namespace std;
//-------读边
const int N=2e4+10,M=2e5+10;
int h[N],e[M],ne[M],w[M],idx;
int n,m;
void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
//-------
//-------染色法判断二分图
int color[N];
bool dfs(int u,int c,int mid)
{
	color[u]=c;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(w[i]<=mid)continue;
		if(!color[j])
		{
			if(!dfs(j,3-c,mid))return false;
		}else if(color[j]==color[u])return false;
	}
	return true;
}
bool check(int mid)//二分判定
{
	memset(color,0,sizeof color);
	for(int i=1;i<=n;i++)
	{
		if(!color[i])
		{
			if(!dfs(i,1,mid))return false;
		}
	}
	return true;
}
//------------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//--------读边
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b,c;cin>>a>>b>>c;
		add(a,b,c);add(b,a,c);
	}
	//-----------
	
	//-------二分满足条件的最小值
	int l=0,r=1e9;
	while(l<r)
	{
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	cout<<r;
	//--------
	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
62
63
64
65
66
67
68
69
70

2、最大匹配数 棋盘覆盖

给定一个 $N$ 行 $N$ 列的棋盘，已知某些格子禁止放置。

求最多能往棋盘上放多少块的长度为 $2$、宽度为 $1$ 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重叠。

输入格式

第一行包含两个整数 $N$ 和 $t$，其中 $t$ 为禁止放置的格子的数量。

接下来 $t$ 行每行包含两个整数 $x$ 和 $y$，表示位于第 $x$ 行第 $y$ 列的格子禁止放置，行列数从 $1$ 开始。

输出格式

输出一个整数，表示结果。

数据范围

$1\le N\le 100$,
$0\le t\le 100$

输入样例：

8 0
1

输出样例：

32
1

我们如何将他与二分图的最大匹配联系起来呢？

首先我先对每一个格子染上颜色：

我们发现如果我们要在一个黑色的格子上放古碑，由于他是$1\times 2$的长方形，所以它必然会占用他相邻$4$个白色格子中的一个。所以求解的问题就出现了：将黑色格子划分到集合$A$,白色格子划分到集合$B$,那么问题就是求二分图的最大匹配数。我们还可以发现黑色格子的横纵坐标加起来为奇数，白色格子的横纵坐标加起来为偶数，所以我们随便枚举一个颜色的格子进行匹配即可。

完整代码:

#include 
using namespace std;
using pii = pair<int,int>;
//---
const int N=110;
bool g[N][N];//表示每个格子是否被禁止
int n,t,ne[][2]={1,0,-1,0,0,1,0,-1};
pii match[N][N];
bool st[N][N];
bool find(int x,int y)
{
	for(int k=0;k<4;k++)//枚举相邻白色方格进行匹配
	{
		int tx=x+ne[k][0];
		int ty=y+ne[k][1];
		if(tx<1||tx>n||ty<1||ty>n||g[tx][ty]||st[tx][ty])continue;
		//越界,禁止,已经被占用都是不符合的,直接continue
		st[tx][ty]=true;
		auto t=match[tx][ty];
		if(t.first==0||find(t.first,t.second))
		{
			match[tx][ty]={x,y};
			return true;
		}
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>t;
	while(t--)
	{
		int x,y;cin>>x>>y;
		g[x][y]=true;//读入禁止方格
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(!g[i][j]&&(i+j)%2)//为没有禁止的,且坐标和为奇数的方格匹配
			{
				memset(st,0,sizeof st);
				if(find(i,j))ans++;//匹配成功答案+1
			}
		}
	}
	cout<<ans;
	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

3、最小点覆盖（König 定理）

最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

我们上边这个二分图$(他的匹配数是3)$来看：

我们只选择了$3$个点，就保证了每一条边的两个端点至少一个在集合中。

结论：二分图中，最小点覆盖 = 最大匹配数。（这里不给予证明）

例题： 机器任务

有两台机器 $A，B$以及 $K$ 个任务。

机器 $A$ 有 $N$ 种不同的模式（模式 $0\sim N-1$），机器 $B$ 有 $M$ 种不同的模式（模式 $0\sim M-1$）。

两台机器最开始都处于模式 $0$。

每个任务既可以在 $A$ 上执行，也可以在 $B$ 上执行。

对于每个任务 $i$，给定两个整数 $a[i]$ 和 $b[i]$，表示如果该任务在 $A$ 上执行，需要设置模式为 $a[i]$，如果在 $B$ 上执行，需要模式为 $b[i]$。

任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。

求怎样分配任务并合理安排顺序，能使机器重启次数最少。

输入格式

输入包含多组测试数据。

每组数据第一行包含三个整数 $N,M,K$。

接下来 $K$ 行，每行三个整数 $i,a[i],和b[i]$，$i$ 为任务编号，从 $0$ 开始。

当输入一行为 $0$ 时，表示输入终止。

输出格式

每组数据输出一个整数，表示所需的机器最少重启次数，每个结果占一行。

数据范围

$N,M<100,K<1000$
$0\le a[i]<N$
$0\le b[i]<M$

输入样例：

5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
1
2
3
4
5
6
7
8
9
10
11
12

输出样例：

3
1

首先我们将每一个任务当成一条边，那么我们想要完成任务$i$，必须要从$a[i]和b[i]$选一个,那么题目的要求就会变成：

选出一个集合，里面放的是机器的模式，使得每个任务（边）的至少一个端点在集合中，那么所求集合的点的数量就是答案。

很明显这是一道 最小点覆盖 的题目，并且图为二分图，所以我们只需求出最大匹配数即可。

完整代码：

#include 
using namespace std;
//-----建边
const int N=1010,M=1010;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
//--------

//-------匈牙利算法
int match[N];bool st[N];
int find(int u)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(st[j])continue;st[j]=true;
		if(!match[j]||find(match[j]))
		{
			match[j]=u;
			return true;
		}
	}
	return false;
}
//------------------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//----------读入建边
	int n,m,k;
	while(cin>>n,n)
	{
		cin>>m>>k;
		memset(h,-1,sizeof h);
		memset(match,0,sizeof match);
		idx=0;
		while(k--)
		{
			int t,a,b;cin>>t>>a>>b;
			if(a==0||b==0)continue;//初始状态为0,所以可以用0解决的就不用求了
			add(a,b);
		}
		//---------------
		int ans=0;
		for(int i=1;i<=n;i++)//开始匹配
		{
			memset(st,0,sizeof st);
			if(find(i))ans++;//匹配成功
		}
		cout<<ans<<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

4、最大独立集

最大独立集：选最多的点，满足两两之间没有边相连。

因为在最小点覆盖中，任意一条边都被至少选了一个顶点，所以对于其点集的补集，任意一条边都被至多选了一个顶点，所以不存在边连接两个点集中的点，且该点集最大。因此二分图中，最大独立集 = $n$ - 最小点覆盖。

例题：骑士放置

给定一个$N\times M$ 的棋盘，有一些格子禁止放棋子。

问棋盘上最多能放多少个不能互相攻击的骑士（国际象棋的“骑士”，类似于中国象棋的“马”，按照“日”字攻击，但没有中国象棋“别马腿”的规则）。

输入格式

第一行包含三个整数 $N,M,T$,其中 $T$ 表示禁止放置的格子的数量。

接下来 $T$ 行每行包含两个整数 $x$ 和 $y$，表示位于第 $x$ 行第 $y$ 列的格子禁止放置，行列数从 $1$ 开始。

输出格式

输出一个整数表示结果。

数据范围

$1\le N,M\le 100$

输入样例：

2 3 0
1

输出样例：

4
1

我们假设每一个点与扩展的8个方向的点都连一条边。

那么题意是问我们在棋盘上可以选出多少点，他们两两之间没有边相连 = > 最大独立集问题

此时我们不能判断是不是二分图问题，现在我们画图研究一下。

我们可以看到，每一个白色点可以攻击到的点一定是黑色点，那么我们就可以当成二分图来做了

黑白格点分别当作二分图的左边点和右边点。

所以答案就是： $n$-最大匹配数$(n为总合法点的数量)$,匹配数的求法和上边的棋盘覆盖一样，改一下$ne[]$数组即可。

#include 
using namespace std;
using pii = pair<int,int>;
const int N=110;
bool g[N][N],st[N][N];
pii match[N][N];
int n,m,t,ne[][2]={-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
//--------------匈牙利算法匹配
bool find(int x,int y)
{
	for(int k=0;k<8;k++)
	{
		int tx=x+ne[k][0];
		int ty=y+ne[k][1];
		if(tx<1||tx>n||ty<1||ty>m||g[tx][ty]||st[tx][ty])continue;
		st[tx][ty]=true;
		auto t=match[tx][ty];
		if(t.first==0||find(t.first,t.second))
		{
			match[tx][ty]={x,y};
			return true;
		}
	}
	return false;
}
//----------------------
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m>>t;
	for(int i=0;i<t;i++)//读入禁止点
	{
		int x,y;cin>>x>>y;
		g[x][y]=true;//禁止放置
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(!g[i][j]&&(i+j)%2)//只枚举白色点
			{
				memset(st,0,sizeof st);
				if(find(i,j))ans++;
			}
		}
	}
	cout<<n*m-t-ans;//最大独立集 = 有效点数 - 最大匹配数
	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