笔试｜二分图最大匹配/最小点覆盖问题（增广路、匈牙利算法）
2022-04-16 本文已影响0人
zilla
参考：https://blog.csdn.net/qq_38956769/article/details/80238896
二分图
- 定义：1）无向图；2）将顶点分为两类，边只存在于两类点之间，不存在于类内顶点间。
若能将无向图G=(V,E)的顶点V划分为两个交集为空的顶点集，并且任意边的两个端点都分属于两个集合，则称图G为一个为二分图。 - 判定：如果一个图是连通的，可以用如下的染色法判定是否二分图：
我们把X部的结点颜色设为0，Y部的颜色设为1。
从某个未染色的结点u开始，做BFS或者DFS 。把u染为0，枚举u的儿子v。如果v未染色，就染为与u相反的颜色，如果已染色，则判断u与v的颜色是否相同，相同则不是二分图。
如果一个图不连通，则在每个连通块中作判定。 - 例子：情侣配对
匹配
在G的一个子图S中，S的边集中的任意两条边都不依附于同一个顶点，则称S是一个匹配。
- 最大匹配
有的人有多个意向，无冲突地情况下尽量多撮合成几对。成功配对数最多的匹配为最大匹配。 - 最优匹配/完美匹配
若每个人都找到了心仪对象。这种撮合方式，叫做最优匹配或完美匹配。
交替路 & 增广路
用于解决新配对时的冲突。交替路即非匹配边、匹配边交替。
一个一个找匹配，出现冲突时，找首尾都是非匹配边的交替路（即，增广路） ，找到后将其取反，此时得到新匹配，匹配点比原先多1个。
匈牙利算法：不断利用增广路找更好的匹配
- 每个点从另一个集合里挑对象，没冲突的话就先安排上，要是冲突了就用增广路径重新匹配。重复上述思路，直到所有的点都找到对象，或者找不到对象也找不到增广路。
- 深度优先和广度优先
上述是深度优先匈牙利算法。就是冲突了立刻用增广路来解决。
另外一种是广度优先匈牙利算法。思路是，冲突了就换一个心仪对象，看另一个心仪对象是不是也配对了，要是都配对了，再用增广路来解决。 - 核心：找增广路（DFS）
对于每个可以与u匹配的顶点v，假如v未被匹配，那直接用 v与u匹配；
如果v已与顶点w匹配，那么调用DFS(w)来求证w是否可以与其它顶点匹配，如果DFS(w)返回 true的话，使v与u匹配；如果DFS(w)返回false,则检查u的下一个邻接点 ······
在DFS 时，要标记访问过的顶点（vis[j]=true），以防死循环和重复计算；每次在主过程中开始一次DFS前，所有的顶点都是未标记。
主过程只需对每个X部的顶点调用DFS ，如果返回一次 true，就对最大匹配数加一；一个简单的循环就求出了最大匹配数目。
/************深搜找增广路************/
bool Vis[MAX_N+1];
int Match[MAX_N+1];
bool Dfs(int u){
for(int i=0;i<Adj[u].size();i++){
int v=Adj[u][i];
if(Vis[v])
continue;
Vis[v]=true;
if(!Match[v]||Dfs(Match[v])){
Match[v]=u;
Match[u]=v;
return true;
}
}
return false;
}
/*********匈牙利算法主函数**********/
void Solve(){
for(int i=1;i<=n;i++){
memset(Vis,false,sizeof(Vis));
if(!Match[i])
if(Dfs(i))
ans++;
}
}
König定理
二分图最小点覆盖的点的数量等于二分图最大匹配的边的数量，即最小点覆盖=最大匹配数。
最小边覆盖（最小的覆盖所有点的边集）=最大独立集（点集，当且仅当它不被包含在一个更大的点集中时）=总节点数-最大匹配数
- 𝐷𝑖𝑛𝑖𝑐 算法
