leetcode(16):匈牙利问题||素数伴侣1. 匈牙利问题2. 素数伴侣问题

68 阅读 0 评论 45 点赞

我是靠谱客的博主优美树叶，最近开发中收集的这篇文章主要介绍leetcode(16):匈牙利问题||素数伴侣1. 匈牙利问题2. 素数伴侣问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

该题第一次接触是在HJ机式中第一次接触：HJ28素数伴侣

该题和匈牙利问题非常相像；先介绍匈牙利问题；

1. 匈牙利问题

一般情况下，可以分为两列的最佳匹配问题，就可以用匈牙利算法来做

这篇文章写得很好：趣写算法系列之–匈牙利算法
下面这篇文章也可以是2017中兴提前批试题；
匈牙利算法——最大匹配问题详解
可以先看上面两篇文章

上面的例子都两列，也就是 m x 2的矩阵，而且更容易理解。而且上面HJ28的题也是两列的。也就是二分图。遇到两列（奇偶分类）+最佳匹配问题就可以考虑匈牙利算法；

二分图定义
设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图

分析：两个偶数之和为偶数，两个奇数之和为偶数，都不能是素数伴侣，所以需要先将奇数偶数分开，然后两两组合，类比于匈牙利问题，就是每一个奇数和每一个偶数配对，要求配对的对数最多。

利用二分图匹配（主要是一个定理，dfs），得出最大的对数

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。