题解 | #素数伴侣#

思路

采用匈牙利算法来完成本题。核心是：能让就让，先到先得。涉及到了 二分图 相关的知识。

代码

#include <iostream>
#include <vector>

using namespace std;

bool isPrime(int num)
{
    if( 1 == num )
        return false;
    for( int i = 2; i*i <= num; i++ )
    {
        if( num % i == 0)
            return false;
    }
    return true;
}

bool match(int x, vector<int> evens, vector<bool>& vis, vector<int>& evensMatch)
{
    // 遍历偶数，检查当前传入的奇数和那些偶数匹配
    for( int i = 0; i < evens.size(); i++ )
    {
        // 如果当前偶数与传入的奇数匹配，且该偶数还没有匹配过奇数
        if( isPrime(x + evens[i]) && !vis[i] )
        {
            vis[i] = true;
            if( evensMatch[i] == 0 || match(evensMatch[i], evens, vis, evensMatch) )
            {
                evensMatch[i] = x;  // 传入的奇数可以作为第 i 个偶数的伴侣
                return true;
            }
        }
    }
    // 遍历完偶数都没有找到匹配得到的，返回匹配失败
    return false;
}

int main()
{
    int n;
    while( cin >> n )
    {
        vector<int> odds, evens;  // 奇数和偶数
        int tmp;
        for( int i = 0; i < n; i++ )
        {
            cin >> tmp;
            if( tmp & 1 == 1 )
                odds.push_back(tmp);
            else
                evens.push_back(tmp);
        }
        
        // 标记偶数和那个奇数匹配了，并记录该奇数的值
        vector<int> evensMatch(evens.size(), 0);
        int res = 0;
        for( int i = 0; i < odds.size(); i++ )
        {
            vector<bool> vis(evens.size(), false);
            if( match(odds[i], evens, vis, evensMatch) )
                res++;
        }
        cout << res << endl;
    }
    return 0;
}