匈牙利算法
接触到这个算法是因为看到了一个题目,叫做素数伴侣。就是说给你你串数字,从中选择两个数字相加,如果他们的和是个素数,那么这一对叫做素数伴侣。然后我们需要找到这串数字中最多能找到多少对素数伴侣。
这个问题的解法首先是把数字分为两部分,一部分是偶数,一部分是奇数,因为两个偶数相加或者两个奇数相加一定还是偶数,不可能是素数。
于是这个问题就变成了分别从偶数中选一个,然后从奇数中选一个,看看最多选出多少对相加为素数。这个问题就用到了匈牙利算法。
匈牙利算法主要用于解决一些与二分图匹配有关的问题,所以我们先来了解一下二分图。