郑州模板建站,网络营销与传统营销相比的优势,建设银行纪念币预约网站,网站开发软件 手机every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog
0. 前言
匈牙利匹配算法
1. 正文
1.1 基础概念
二分图
顶点分为两个集合#xff0c;集合间顶点相连#xff0c;集合内点不相连 匹配
一个匹配就是一个边的…every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog
0. 前言
匈牙利匹配算法
1. 正文
1.1 基础概念
二分图
顶点分为两个集合集合间顶点相连集合内点不相连 匹配
一个匹配就是一个边的集合其中任意两条边不存在公共的顶点
最大匹配
上图中我们能找到多组匹配在这其中所含匹配变数最多的的匹配成为最大匹配。
交替路
从一个未匹配的点出发依次经过非匹配边匹配边非匹配边这样形成的路称为交替路
增广路
从一个未匹配的点出发走交替路如果途径另一个未匹配点起点不算则这条交替路称为增广路
1.2 算法流程
1.2.1 通俗理解
概括 先到先得能让则让
对于如下已有的匹配我们需要寻找他的最大匹配。
1.2.2 步骤
下面以经典的配对情景进行说明。
现在有boys和girls两个点集每个人有各自的暧昧对象可能有多个现在要把他们配情侣最多能配多少对即寻找最大匹配数
说明
边表示暧昧关系
注意
不能搞基哦不能脚踏多只船 先从B1看起他与G2有暧昧那么先暂时他们配成一对。 注意 这里突出了先到先得 再看B2B2也可G2纠缠不清那么我们看G2现在有男友吗有的是B1。那B1有没有其他暧昧对象呢花心男果然是花心男还有一个G4同时G4还没有安排对象。那么把B1和G4配成一对。
注意 这里突出了能让则让 再接着我们看B3他这G1直接配对就好。
最后我们看B4他的暧昧对象是G4但是G4现在已经有男友了。按照之前的思路往前到看看能不能让一让的。发现没法让所以B4只能单着了。 同时G3也只能单着。
注意 这里依然是能让则让让不了也没法 至此找到一个了最大匹配但是最大匹配不是固定的。如果从girls这边开始或者从B4开始情况可能就不一样了。但是最大匹配数是一样的。
1.2.3 代码实现
int M,N; // M,N 分表表示左右则集合的元素个数
int Map[MAXM][MAXN]; // 邻接矩阵存图
int p[MAXN]; // 记录当前右侧元素所对应的左侧元素
bool vis[MAXN]; // 记录右侧元素是否已被访问过bool match(int i){for(int j1;jN;j){ // 有边且未访问if(Map[i][j]!vis[j]){ vis[j] true; // 记录访问过// 无匹配 或者 原匹配左侧元素可以找到新的匹配if(p[j]0 || match(p[j])){ p[j]i; // 当前左侧元素成为当前右侧元素的新匹配return true // 返回匹配成功}}}return false;
}int Hungarian(){int cnt 0;for(int i1; iN; i){memset(vis,false,sizeof(vis)); // 重置vis数组if(match(i)) cnt;}return cnt
}1.3 最小点覆盖问题
另外一个关于二分图的问题是求最小点覆盖我们想找到最少的一些点使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是删除包含这些点的边可以删掉所有边。 König定理: 一个二分图中的最大匹配数等于这个图中的最小点覆盖数。 1.4 应用
1.4.1 案例一
题目 面对OIBH组织的嚣张气焰, 柯南决定深入牛棚, 一探虚实. 他经过深思熟虑, 决定从OIBH组织大门进入… OIBH组织的大门有一个很神奇的锁. 锁是由M*N个格子组成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子给按下去. 如果柯南能在组织限定的次数内将所有格子都按下去, 那么他就能够进入总部. 但是OIBH组织不是吃素的, 他们的限定次数恰是最少次数. 请您帮助柯南计算出开给定的锁所需的最少次数.
读入/Input
第一行 两个不超过100的正整数N, M表示矩阵的长和宽 以下N行 每行M个数 非0即1 1为凸起方格
输出/Output
一个整数 所需最少次数 如果我们把样例的矩阵转化为二分图的形式是这样的 按下一行或一列其实就是删掉与某个点相连的所有边。现在要求最少的操作次数想想看这不就是求最小点覆盖数吗所以直接套匈牙利算法即可。代码略。
参考
https://zhuanlan.zhihu.com/p/96229700https://zhuanlan.zhihu.com/p/62981901
