1.什么是二分图

如果图 $G=(V,E)$ 的顶点集 $V$ 可以分为两个互不相交的子集 $X$ 和 $Y$ ，使得每条边 $e\in E$ 的两个端点都分别属于 $X$ 和 $Y$ ，就称图 $G$ 是一个二分图。集合 $X$ 和 $Y$ 常称作它的两个部分，或者分别称为二分图的左部和右部。

这是 OI Wiki 上的解释，简单说就是当一个图的所有顶点可以分成两个集合，使得每个集合中不存在两个顶点之间有边，这个图就是二分图。

举个例子：

可以看到左边的三个顶点间是没有边的，右边也如此。所以这个图就是二分图。

不难看出，可以给这个二分图进行黑白染色，即左边全染成白色，右边全染成黑色。

由于这个性质，可以得出一个结论：在二分图中不存在奇数长度的环。因为无论从哪个颜色节点的顶点开始，它的邻居节点都是与他异色的。所以每走一步就会换一次颜色。若想要再次回到这个节点，就必须走偶数长度的环。

2.二分图染色

因为二分图能被黑白染色，所以可以通过黑白染色来判断一个图是否是二分图。

大体思路如下：

遍历所有顶点，若出现未被染色的顶点，就说明存在未被染色的连通分量。
任选一种颜色给这个顶点染色，并以它为起点做 DFS 或 BFS。
若走到了一个未被染色的顶点，将其染上与前一个顶点相反的颜色。
若走到了一个被染色的点，如果它的颜色与前一个顶点相反，则继续遍历；如果相同，则证明这个图不是二分图。

找个板子题来具体说明一下：封锁阳光大学。

将放或不放河蟹看做黑白两种颜色，并对图进行染色。再把黑看做放河蟹和把白看做放河蟹的两种情况进行比较，取最小值，这些最小值的和就是答案。

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
vector<int> G[maxn];
int n,m,ans=0,c[maxn],sum=0; 
bool flag[maxn];
void DFS(int u,int k){  //染色
	if(c[u]==k) return;  //如果与前面顶点颜色不同
	if(c[u]!=-1){  //如果与前面顶点颜色相同
		cout<<"Impossible";
		exit(0);
	}
	c[u]=k;  //染色
	flag[u]=1;
	sum++;
	for(int i:G[u]) DFS(i,k^1);  //遍历并改变颜色
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
    	int x,y;
    	scanf("%d%d",&x,&y);
    	G[x].push_back(y);
    	G[y].push_back(x);
	}
	memset(flag,0,sizeof(flag));
	for(int i=1;i<=n;++i){
		if(flag[i]) continue;
		sum=0;
		memset(c,-1,sizeof(c));  //用时间戳更好，但用memset能刚好AC
		DFS(i,0);
		int p=0;
		for(int i=1;i<=n;++i) p+=c[i]==1;
		ans+=min(p,sum-p);  //白或者黑
	}
	cout<<ans;
    return 0;
}

3.最大匹配（匈牙利算法）

如果对于边的全集中有一个子集满足其中任意两条边没有公共顶点，则称这个子集为这个图的一组匹配。可以理解为当且仅当一个顶点与另一个顶点有边。在二分图中，可以把匹配理解为在一组匹配中，左边的顶点只有一个右边的顶点有边。

在所有匹配中，包含边数最大的一个匹配被称为最大匹配。~~显然，在二分图中最大匹配边数不大于二分之一的顶点数。~~

求最大匹配的核心思想其实就是 DFS。

大体思路如下：

遍历每一个左边的顶点。
遍历每个左边顶点与右边顶点连的所有边。
如果当前访问的右边顶点未被匹配，则暂时将它们匹配。
如果当前访问的右边顶点已被匹配，让原本与其已经匹配的左侧顶点重新匹配。若那个左侧顶点存在额外的匹配，则将其与新的右侧顶点暂时匹配，现在的左侧顶点与现在被访问的右侧顶点暂时匹配。若不存在新的匹配，则遍历下一条边，直到遍历结束为止。

~~可能说的不太清楚~~

如果没有看懂可以去看看这篇文章。

模板题：二分图最大匹配。

我们可以根据以上思路写出代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,e,r[505],ans=0;  //r[i]表示第i个右边顶点与哪个左边顶点匹配
bool G[505][505],used[505];  //used[i]表示这个左边顶点与第i个右边顶点是否匹配
bool find(int x){
	for(int i=1;i<=m;++i){
		if(G[x][i]&&!used[i]){  //遍历边
			used[i]=1;
			if(r[i]==0||find(r[i])){  //如果为匹配或者能被腾出
				r[i]=x;  //匹配
				return true;
			}
		}
	}
	return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;++i){
    	int x,y;
    	scanf("%d%d",&x,&y);
    	G[x][y]=1;
	}
	for(int i=1;i<=n;++i){  //遍历顶点
		memset(used,0,sizeof(used));
		if(find(i)) ans++;  //如果能匹配，总长度增加
	}
	cout<<ans;
    return 0;
}

例题：座位安排。

这道题几乎是个板子，但是要注意，每排有两个座位，所以可以考虑将另一列座位安在第一列的尾部，然后就是愉快的打板子。

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
vector<int> G[4010];
int n,r[4010],ans=0;
bool used[4010];
bool find(int x){
	for(int i:G[x]){
		if(used[i]) continue;
		used[i]=1;
		if(r[i]==0||find(r[i])){
			r[i]=x;
			return true;
		}
		if(used[i+n]) continue;
		used[i+n]=1;
		if(r[i+n]==0||find(r[i+n])){
			r[i+n]=x;
			return true;
		}
	}
	return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=2*n;++i){
    	int x,y;
    	scanf("%d%d",&x,&y);
    	G[i].push_back(x);
    	G[i].push_back(y);
	}
	for(int i=1;i<=2*n;++i){
		memset(used,0,sizeof(used));
		if(find(i)) ans++;
	}
	cout<<ans;
    return 0;
}

有人说这个算法与网络流有关，可惜我不会。。。

二分图学习笔记

文章操作

1.什么是二分图

2.二分图染色

AC Code：

3.最大匹配（匈牙利算法）

AC Code：

相关推荐

评论

二分图学习笔记