二分图

前情提要：今日速查打二分图最大匹配，发现自己的匈牙利算法《学的非常好》，于是一怒之下写了这篇笔记

1.什么是二分图？

若一张无向图\(G\)的\(N\)个节点可分成\(A、B\)两个不相交的非空集合，并且同一集合内的点之间没有边相连，那称该图为二分图

性质：二分图中不存在奇环（一个点想回到自己的点集肯定会经过奇数条边）

2.二分图判定

1）染色法

从一个节点\(u\)染色，并把与其相连的所有点染上异色，若最后发现存在一个点被染上了两种不同颜色，则证明该图不是二分图，否则一定是二分图

实现：\(dfs\)

inline bool dfs(int u,int c){
	col[u]=c;
	for(auto v:G[u]){//分两类讨论:v点已被染色和未被染色.一定要从每个点出发把每条边都验证一下
		if(col[v] && col[v]==c) return 0;
		if(!col[v] && !dfs(v,3-c)) return 0;
	}
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	F(i,1,m){
		scanf("%d %d",&u,&v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	if(dfs(1,1)) puts("YES");
	else puts("NO");
	return 0; 
}

2）扩展域并查集

扩展域并查集用以解决多个逻辑冲突问题：有两个集合，n个ai和bi,m个形如(ai,bi)的条件表示ai和bi不在同一集合中，问最终能否达到

思想：约束\(a,b\)不在一个集合中即就是将\(a\)与\(\neg b\)放入放入同一集合内，再将\(b\)与\(\neg a\)放入同一集合内,最后检查\(a\)与\(\neg a\),\(b\)与\(\neg b\)是否在同一集合中即可,实际编程中\(merge(a,\neg b)\)就是\(merge(a,b+n)\)

#include<bits/stdc++.h>
using namespace std;
#define F(i,l,r) for(int i=l;i<=r;++i)
const int N=205,M=5005;
int n,m,u,v,fa[N<<1];//并查集开两倍空间 
inline int getfather(int x){
	if(fa[x]!=x) fa[x]=getfather(fa[x]);
	return fa[x];
}
inline void add(int x,int y){
	x=getfather(x),y=getfather(y);
	if(x!=y) fa[x]=y; 
}
inline bool chk(int x,int y){ return getfather(x)==getfather(y); }
int main(){
	scanf("%d%d",&n,&m); F(i,1,n*2) fa[i]=i;
	F(i,1,m) {
		scanf("%d%d",&u,&v); ++u,++v;	
		if(u>v) swap(u,v);
		add(u,v+n);
	}
	F(i,1,n) if(chk(i,i+n)) return puts("NO"),0;
	puts("YES");
	return 0;
}

二分图最大匹配

对于G的子图M，若M中任意两边都没有公共端点，则称M是二分图的一种匹配，所有匹配中包含边数最多的一组匹配成为二分图的最大匹配

1）匈牙利算法：

思想：通过不断找增广路寻找更大的匹配，若无法找到增广路了，当前匹配就是最大匹配

交替路：非匹配边--->匹配边--->非匹配边--->匹配边--->非匹配边--->匹配边--->......

增广路：从非匹配点出发沿交替路到达另一非匹配点的路径

性质：增广路上的非匹配边总比匹配边多一条（两两为一组，最后一条非匹边会剩下），故 非匹 与 已匹 互换身份就能使匹配变大

实现：\(dfs\)(参考代码)或\(bfs\)

inline bool dfs(int u){
	for(int i=first[u];i;i=e[i].ne){
		int v=e[i].v; if(vis[v]) continue;vis[v]=1;
		if(!match[v] || dfs(match[v])) return match[v]=u,1;
	}
	return 0;
}
	idx=0,sum=0; mem(e); mem(match); mem(first);
	scanf("%d%d%d",&k,&m,&n); int u,v;
	F(i,1,k){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	F(i,1,m){
		mem(vis);
		if(dfs(i)) ++sum;
	}
	printf("%d\n",sum);

最坏情况下以每个点为起点寻找增广路会遍历整张图每条边(continue也会耗时所以注意不是\(O(N)\)),时间复杂度为\(O(M)\),故总时间复杂度为\(O(NM)\)

2）\(Dinic\)算法：学了再说

再忘我就再写，我还不信了这么简单个算法我能记不住？