题解 | #素数伴侣#

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

//判断一个数是否为素数
bool isprime(int num){
    if(num<2)return false;
    for(int i=2;i<=sqrt(num);++i){
        if(num%i==0)return false;
    }
    return true;
}
//尝试为左侧的点找配对
bool find(vector<vector<int>>&graph,int u,vector<bool>&visited,vector<int>&match){
    //二分图传入，奇数组u节点传入，访问标记组传入，匹配记录组传入
    for(int v:graph[u]){//遍历奇数组u对应的所有可配对的偶数节点v
        if(!visited[v]){//如果当前偶数组v节点没有被访问
            visited[v]=true;//打上访问标记
            if(match[v]==-1||find(graph,match[v],visited,match)){
                //如果当前偶数组v节点没有被匹配过或者原来匹配过但是找到了其他新的路径
                match[v]=u;//偶数组v节点匹配到了奇数组u节点
                return true;//返回匹配新路径成功
            }
        }
    }
    return false;//没有找到新匹配的路径
}

int main() {
    int n;
    cin>>n;
    vector<int>numbers(n);
    vector<int>odd,even;//偶数组v,奇数组u
    //分类成两组
    for(int i=0;i<n;++i){
        cin>>numbers[i];
        if(numbers[i]%2==0){
            even.push_back(numbers[i]);
        }
        else{
            odd.push_back(numbers[i]);
        }
    }
    //构建二分图
    vector<vector<int>>graph(odd.size());
    for(int i=0;i<odd.size();++i){
        for(int j=0;j<even.size();++j){
            if(isprime(odd[i]+even[j])){
                graph[i].push_back(j);
            }
        }
    }
    //匈牙利算法求最大匹配
    int ans=0;
    vector<int>match(even.size(),-1);
    for(int i=0;i<odd.size();++i){
        vector<bool>visited(even.size(),false);
        if(find(graph,i,visited,match)){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")