二分图

定义

给出一张图（通常是无向图），如果存在一种方案让这个图满足以下性质：

• 将图中的点分为两个点集，分别为左点集和右点集。
• 没有任意一条边的端点来自同一个点集。

那么我们称这张图为二分图。

换一种说法，如果将图中的边理解为两人之间关系的话：

如果可以将一张图中的点分为男生和女生且不存在同性恋关系(SP3377 A Bug's Life)，那么这张图为二分图。

比如说这就是一张二分图。

这不是二分图。

有一点需要记住，那就是 所有的树都是二分图。

判断

二分图的判断很简单，用 染色法 即可。根据二分图的定义，我们感性理解就可以得到如果这张图是二分图，那么相邻两点的颜色一定不同。

就拿上面这张图举例。

首先枚举第 1 个点：

1. 给第 1 个点染白色（用 1 表示）。
2. 发现第 1 个点连向第 2 个点以及第 3 个点，它们都没有染上色，所以给它们都染上黑色（用 2 表示）。

接着去看第 2 个点：

1. 第 2 个点已经被染色，所以不用再继续染色。
2. 发现第 2 个点连向第 1 个点以及第 3 个点，第 1 个点是白色，符合条件。但是第 2 个点连向了第 3 个点，第 2 个点和第 3 个点都是黑色，不满足二分图的条件，所以这张图不是二分图。

过程就是这么简单，接下来看代码。

我们以 洛谷P1330 封锁阳光大学 为例。

1 存图以及加边

这里我用的链式前向星存图。

如果不知道什么是链式前向星的话，可以左转看这里。

2 核心部分

比较好理解的代码，采用 DFS 完成二分图判断。

由于这道题需要我们求最小的河蟹数量，感性的理解就用两个变量 (x),(y) 记录左点集和右点集的点的数量，求出 (x) 和 (y) 的最小值就是答案。

还要注意这道题的图可能不是连通的，会产生多个二分图，需要多次判断。

DFS部分：

void dfs(int u,int c)//二分图染色+判断 
{
	color[u]=c;//染色 
	if(color[u]==1)	x++;//记录点集1 
	if(color[u]==2)	y++;//记录点集2 
	for(int i=head[u];i;i=e[i].nxt)//遍历以i为起点的每一条边 
	{
		int j=e[i].to;//终点 
		if(color[j]>0)//如果j点已经染色 
		{
			if(color[j]==c)//如果j点的颜色和起点颜色c相同，不满足二分图性质 
				f=1;
		}
		else dfs(j,3-c);//继续染色 
	}
}

3 完整代码

#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,f,x,y,ans;
struct edge
{
	int to,nxt;
} e[2*100005];
int head[100005],color[100005],cnt;
void init()//初始化函数 
{
	for(int i=0;i<=n;i++)	head[i]=-1;
	cnt=0;
}
void add(int u,int v)//链式前向星加边 
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void dfs(int u,int c)//二分图染色+判断 
{
	color[u]=c;//染色 
	if(color[u]==1)	x++;//记录点集1 
	if(color[u]==2)	y++;//记录点集2 
	for(int i=head[u];i;i=e[i].nxt)//遍历以i为起点的每一条边 
	{
		int j=e[i].to;//中点 
		if(color[j]>0)//如果j点已经染色 
		{
			if(color[j]==c)//如果j点的颜色和起点颜色c相同，不满足二分图性质 
				f=1;
		}
		else dfs(j,3-c);//继续染色 
	}
}
int main()
{
	init();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)
	{
		if(!color[i])//无向图不一定连通，需要多次搜索 
		{
			x=y=0;
			dfs(i,1);
			if(f==0)	ans+=min(x,y);	
		}
	}
	if(f==1)	printf("Impossiblen");
	else	printf("%dn",ans);
}

二分图最大匹配

1 定义

在二分图的边集中选出一个子集，使得子集中所有边的节点互不相交。

2 求二分图最大匹配

用 匈牙利算法 求解。匈牙利算法分为DFS版本和BFS版本，DFS较为好理解，BFS效率更高。

先介绍DFS基本实现过程。我们以这张图为例。

首先看 3 号点：

1. 3 号点连向 2 号点以及 4 号点。因为 2 号点没有被访问过，且 2 号点没有与它匹配的点。所以我们记录 2 号点的匹配点是 3 号点。

接着看 1 号点：

1. 1 号点连向 2 号点以及 4 号点。因为 2 号点没有被访问过，但是 2 号点已经有与它相匹配的 3 号点了。这时候该怎么办？
2. 我们考虑给 2 号点当前匹配的点 ———— 3 号点换一个匹配的点，我们发现 3 号点还连向了 4 号点，所以我们将 3 号点与 4 号点相匹配。
3. 这样就可以将 1 号点与 2 号点相匹配了。

所有的左部点都遍历了，循环结束，求出答案为 2。

3 完整代码

洛谷P3386 [模板]二分图最大匹配

#include<bits/stdc++.h>
using namespace std;
int n,m,num,u,v,t,vis[5050],a[5050],ans;
//vis[i]表示 i 点是否被访问过。
//a[i]表示 i 点相连的左部点的编号。
//t表示时间标记，会用在vis[i]的判断中。如果觉得复杂，可以在每一轮搜索的时候memset一下，但是要注意时间复杂度。
struct edge
{
	int to,nxt;
} e[100000];
int head[505],cnt;
void add(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
bool fnd(int x)
{
	for(int i=head[x];i;i=e[i].nxt)
	{
		if(vis[e[i].to]==t)	continue;//如果已经访问过了
		vis[e[i].to]=t;//更新时间标记
		if(!a[e[i].to]||fnd(a[e[i].to]))//如果e[i].to这个点还没有相匹配的点 或者 e[i].to这个点相匹配的点可以找到另一个右部点来匹配
		{
			a[e[i].to]=x;
			return true;
		}
	}
	return false;
}
int main()
{
	scanf("%d%d%d",&n,&m,&num);
	for(int i=1;i<=num;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);//注意这里加有向边 
	}
	for(int i=1;i<=n;i++)
	{
		t=i;//记得更新时间标记
		if(fnd(i))	ans++;
	}
	printf("%dn",ans);
}

二分图最小点覆盖

1 定义

从二分图点集中选出一个子集，使得二分图中的边至少有一个端点在子集中。这样的子集中点数最少的就称为二分图最小点覆盖。

2 定理

二分图最小点覆盖=二分图最大匹配数。

二分图最大独立集

1 定义

从二分图点集中选出一个子集，使得子集中的点两两没有边相连。这样的子集中点数最多的就称为二分图最大独立集。

2 定理

二分图最大独立集=点总数-二分图最小点覆盖数。

二分图最大加权匹配

二分图最大加权匹配

题单

洛谷：二分图