题解C++ | #素数伴侣#

#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

bool is_susu(const int & a)
{
    for (int i = 2; i <= sqrt(a); i++)
    {
        if (a % i == 0)
            return false;
    }
    return true;
}

bool is_ousu(const int & a)
{
    if (a % 2 == 0)
        return true;
    return false;
}
// 记录素数伴侣的二维数组
int list[100][100] = {0};
// 偶数表
vector<int> os;
// 奇数表表
vector<int> js;
// 记录奇数对应的偶数
int match[100];
// 记录当前奇数是否被访问过
int vst[100] = {0};
bool is_match(int i)
{
    for (uint j = 0; j < js.size(); j++)
    {
        if (list[i][j] == 1 && vst[j] == 0)
        {
            vst[j] = 1;
            if (match[j] == -1 || is_match(match[j]))
            {
                match[j] = i;
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    vector<int> vn(n);
    memset(match, -1, 400);
    int count = 0;
    for (uint i = 0; i < n; i++)
    {
        cin >> vn[i];
        if (is_ousu(vn[i]))
            os.push_back(vn[i]);
        else
            js.push_back(vn[i]);
    }

    for (uint i = 0; i<os.size(); i++)
    {
        for (uint j = 0; j<js.size(); j++)
        {
            if (is_susu(os[i]+js[j]) == true)
            {
                list[i][j] = 1;                
            }
        }
    }
    for (uint i = 0; i < os.size(); i++)
    {
        memset(vst, 0, 100);
        if (is_match(i))
        {
            count += 1;
        }
    }
    cout << count;
}
// 64 位输出请用 printf("%lld")

二分图问题：匈牙利算法的最大匹配问题，

注：最大匹配 == 最小点覆盖