二分图
前情提要：今日速查打二分图最大匹配，发现自己的匈牙利算法《学的非常好》，于是一怒之下写了这篇笔记
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\)算法：学了再说
再忘我就再写，我还不信了这么简单个算法我能记不住？