题解 | #素数伴侣#

#include<iostream>
#include<vector>
using namespace std;
bool isprime(int num)
{
    for(int i = 2; i * i <= num; i++)
        if(num % i == 0)return false;
    return true;
}
bool find(int index, vector<bool>& used, vector<int>& match, vector<vector<bool>>& map)
{
    for(int i = 0; i < used.size(); i++)//遍历每个偶数与奇数比较
        if(map[i][index] && !used[i])
        { //直接查询能否构成
            used[i] = true;
            if(match[i] == -1 || find(match[i], used, match, map))
            { //如果第i个偶数还未配对，或者跟它配对的奇数还有别的选择
                match[i] = index; //则配对该数
                return true;
            }
        }
    return false;
}
int main()
{
    int n;
    while(cin >> n)
    {
        vector<int> odds,evens,nums(n);
        for(int i = 0; i < n; i++)
        {
            cin >> nums[i];
            if(nums[i] % 2)odds.push_back(nums[i]);
            else evens.push_back(nums[i]);
        }
        int count = 0;
        if(odds.size() == 0 || evens.size() == 0)//缺少奇数或者偶数无法构成素数
        {
            cout << count << endl;
            continue;
        }
        vector<vector<bool>> map(evens.size(), vector<bool>(odds.size(), false));
        for(int i = 0; i < evens.size(); i++)//构建所有能相连的奇数偶数的边
            for(int j = 0; j < odds.size(); j++)
                if(isprime(evens[i] + odds[j]))
                    map[i][j] = true;
        vector<int> match(evens.size(), -1); //统计每个偶数的配对是哪个奇数
        for(int i = 0; i < odds.size(); i++)
        {
            vector<bool> used(evens.size(), false);
            if(find(i, used, match, map))count++;
        }
        cout << count << endl;
    }
}