题解 | #素数伴侣#

#if 0
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

/* 素数：大于1的质数，即只能被1和它本身整除 */
bool primeNums(int first, int second) 
{
    int sum = first + second;
    bool flag = true;
    if(sum == 1 || sum == 2) {
        return false;
    } 
    //sqrt是开平方的函数，举个简单的例子：sqrt(4) = 2； sqrt(9) = 3；
    for(int i = 2; i <= sqrt(sum); i++) { 
        if(sum % i == 0) { //非素数
            flag = false;
            break;
        }
    }
    return flag;
}

/*
* 递归排列查找素数伴侣
* 思想：对输入的数组进行排序，对2个数据为一对数据相加的和是否为素数，若为素数，则素数伴侣个数count加1，
*     如果素数伴侣最大值maxx小于count,则count赋值于maxx；对数组进行递归排序
* 步骤：
* 第一步：输入数组个数和数组值
* 第二步：对数组进行排序sort
* 第三步：遍历查找一对数据的和是否为素数伴侣，若为素数，则素数伴侣个数count加1； 
      如果素数伴侣最大值maxx小于count,则count赋值于maxx；
      循环对数组进行递归排序next_permutation
*/
int maxPrimeMate(int *inputVec, int num)
{
    int maxValue = 0;
    sort(inputVec, inputVec+num);
    do {
        int count = 0;
        for(int i = 0; i < num; i+=2) {
            if(primeNums(inputVec[i], inputVec[i+1])) {
                count++;
            }
        }

        if(maxValue < count) {
            maxValue = count;
        }
        
    } while(next_permutation(inputVec, inputVec+num)); //下一组排列
    return maxValue;
}

int main()
{
    int num;
    while(cin>>num) {
        int maxValue = 0;
        int *inputVec = new int[num];
        for(int i = 0; i < num; i++) {
            cin>>inputVec[i];
        }

        if(num % 2 == 0) {
            maxValue = maxPrimeMate(inputVec, num);
            cout<<maxValue<<endl;
        } else {
            cout<<maxValue<<endl;
        }
        delete inputVec;
    }
    return 0;
}


#else
#include <bits/stdc++.h>
using namespace std;
//判断一个数是否为素数
bool IsPrimer(int sum)
{
    bool flag = true;
    if(sum == 1 || sum == 2) {
        return false;
    } 
    //sqrt是开平方的函数，举个简单的例子：sqrt(4) = 2； sqrt(9) = 3；
    for(int i = 2; i <= sqrt(sum); i++) { 
        if(sum % i == 0) { //非素数
            flag = false;
            break;
        }
    }
    return flag;
}
//匈牙利算法，为某一个目标奇数找到它的素数伴侣（偶数）,皆以下标表示
bool FindMate(const int& n, vector<vector<bool>>& map, vector<int>& match, vector<bool> &vis)
{
    for (int i = 0; i < match.size(); i++)
    {
        if (!vis[i] && map[i][n])//偶数未被访问过并且能与目标奇数组成素数（有关系）
        {
            vis[i] = true;
            if (match[i] == -1 || FindMate(match[i], map, match, vis))//当前偶数没有匹配或能给被抛弃的奇数找到新的偶数
            {
                match[i] = n;//找到这个偶数
                return true;
            }
        }
    }
    return false;
}
 
int main()
{
    int num = 0;
    while (cin >> num)
    {
        int count = 0;//匹配对数
        vector<int> even;//偶数
        vector<int> odd;//奇数
        int val = 0;
        //读取数据
        for (int i = 0; i< num; i++)
        {
            cin >> val;
            if (val % 2 == 0) { //偶数
                even.push_back(val);
            } else { //奇数
                odd.push_back(val);
            }
        }
        if (odd.empty() || even.empty())
        {
            cout << count << endl;
            continue;
        }
        //建立关系表，图中的边
        vector<vector<bool>> map(even.size(), vector<bool>(odd.size(), false));
        for (int i = 0; i < even.size(); i++)
        {
            for (int j = 0; j < odd.size(); j++)
            {
                if (IsPrimer(even[i] + odd[j])) //对素数进行判断
                {
                    map[i][j] = true;
                }
            }
        }
        
        if(num % 2 == 0) {
            //建立初始匹配表
            vector<int> match(even.size(), -1);   
            //为每一个奇数都尝试去找对应的偶数，   
            for (int i = 0; i < odd.size(); i++)
            {
                vector<bool> vis(even.size(), false);//每一次查找都相当于重新分配，标志要清零
                if (FindMate(i, map, match, vis))
                {
                    count++;
                }
            }
            cout << count << endl;
        } else {
            cout << count << endl;
        }
        
        
    }
}
 

#endif