题意:给你n个正整数,一对和为素数的数为一个合法数对。你选不超过K个合法数对,使得你选的数对涉及到的数的数量最大化。输出这个值。
所有1之间是可以任意两两配对的。
把奇数放在左侧,偶数放在右侧。
考虑当前要使用多少个“1”,动态更新最大匹配。
如果K不超过 最大匹配数 + 剩下的还没使用过的1数/2 ,那么直接输出这个和*2即可。
否则剩下的用剩余的1(最多一个)+没被匹配上的但是不孤立(有边)的点数 补齐,这样不断更新答案。
有一个坑点是如果1恰好只有一个的话,而且没有能和它加起来组成素数的数的话,就要忽略掉这个1。
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int T,n,K,a[3005];
bool notprime[2000005];
bool cmp(const int &a,const int &b){
return a>b;
}
int e,first[3005],next[3005*3005],v[3005*3005];
void AddEdge(int U,int V){
v[++e]=V;
next[e]=first[U];
first[U]=e;
}
int mat[3005],yi;
bool vis[3005];
bool dfs(int U)
{
for(int i=first[U];i;i=next[i]){
if(!vis[v[i]]){
vis[v[i]]=1;
if(mat[v[i]]==-1 || dfs(mat[v[i]])){
mat[v[i]]=U;
return 1;
}
}
}
return 0;
}
int ru[3005],ru1[3005],right1,right2;
int main(){
notprime[1]=1;
for(int i=2;i<=2000000;++i){
for(ll j=(ll)i*(ll)i;j<=2000000ll;j+=(ll)i){
notprime[j]=1;
}
}
scanf("%d",&T);
for(;T;--T){
e=0;
memset(mat,-1,sizeof(mat));
memset(first,0,sizeof(first));
memset(ru,0,sizeof(ru));
memset(ru1,0,sizeof(ru1));
scanf("%d%d",&n,&K);
yi=0;
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
if(a[i]==1){
++yi;
}
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(!(a[i]==1 && a[j]==1) && !notprime[a[i]+a[j]]){
if(a[i]&1){
AddEdge(i,j);
++ru[j];
if(a[i]==1){
++ru1[j];
}
}
else{
AddEdge(j,i);
++ru[i];
if(a[j]==1){
++ru1[i];
}
}
}
}
}
bool tp=(yi==1 ? 1 : 0);
right1=right2=0;
for(int i=1;i<=n;++i){
if(!(a[i]&1)){
if(ru[i]>ru1[i]){
++right1;
}
if(ru[i]){
++right2;
}
if(ru1[i]){
tp=0;
}
}
}
if(tp){
yi=0;
}
int sum=0,cnt=0,nowleft=0,ans=0;
for(int i=1;i<=n;++i){
if((a[i]&1)){
++nowleft;
if(a[i]!=1 && first[i]){
memset(vis,0,sizeof(vis));
if(dfs(i)){
++sum;
}
}
else if(a[i]==1 && !tp){
if(!cnt){
if(K<=sum+yi/2){
ans=max(ans,2*K);
}
else{
ans=max(ans,2*sum+yi+min(K-sum-yi/2-yi%2,nowleft-1+right1-sum*2));
}
}
++cnt;
memset(vis,0,sizeof(vis));
if(dfs(i)){
++sum;
}
if(K<=sum+(yi-cnt)/2){
ans=max(ans,2*K);
}
else{
ans=max(ans,2*sum+(yi-cnt)+min(K-sum-(yi-cnt)/2-(yi-cnt)%2,nowleft+right2-sum*2));
}
}
}
}
if(!cnt){
if(K<=sum){
ans=max(ans,2*K);
}
else{
ans=max(ans,2*sum+min(K-sum,nowleft+right1-sum*2));
}
}
printf("%d\n",ans);
}
return 0;
}