pta 乐子人游戏

题解：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2010,M=2000000;
int etop=0;
vector<int> match(N,0);
struct EDGE{
    int u,v;
    EDGE* next;
}edge[M];
struct NODE{
    EDGE* fir;
}node[N];
void add_edge(int a,int b){
    edge[etop]={a,b,node[a].fir};
    node[a].fir=&edge[etop];
    etop++;
}
bool find(int x,vector<bool>& vis){
    EDGE* e=node[x].fir;
    while(e!=nullptr){
        int j=(e->v);
        if(!vis[j]){
            vis[j]=true;
            if(!match[j]||find(match[j],vis)){
                match[j]=x;
                return true;
            }
        }
        e=e->next;
    }
    return false;
}
int main(){
    vector<int> prim;
    vector<int> prime(N,0);
    vector<int> notp(N,0);
    notp[1]=1;
    int n,maxi=-1,score1=0,score2=0;
    cin>>n;
    vector<int> a(n,0),b(n,0),c;
    for(int i=0;i!=n;++i){
        cin>>a[i];
        maxi=max(a[i],maxi);
    }
    for(int i=0;i!=n;++i){
        cin>>b[i];
        maxi=max(b[i],maxi);
    }
    for(int i=1;i<=2*maxi;++i){
        if(!notp[i]){
            prime[i]=1;
            prim.push_back(i);
        }
        for(int q=0;q!=prim.size();++q){
            if(prim[q]*i>2*maxi) break;
            notp[prim[q]*i]=1;
            if(i%prim[q]==0) break;
        }
    }
    for(int i=0;i!=n;++i){
        for(int j=0;j!=n;++j){
            if(prime[a[i]+b[j]]) add_edge(i+1,j+1);
        }
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        vector<bool> vis(N,false);
        if(find(i,vis)) ans++;
    }
    cout<<ans<<endl;
    return 0;
}