2023NOIP A层联测17-黑暗料理

本文主要是介绍2023NOIP A层联测17-黑暗料理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简要题意：在 $n$ 个数中选尽可能多的数，使得任意两个数之和不是质数。

$n\le750,a_i\le10^9$

两个数之和为质数，说明两个数一奇一偶，或者都是 $1$ 。

把重复的 $1$ 删去，因为后面不会同时选多个 $1$ 。

建立二分图，奇数放在左边，偶数放在右边，若两个数之和为质数，就连一条边。这里用 $\text{miller rabin}$ 判断。

我们的目标是删去尽可能少的点及其相邻的边，使所有边都被删去。这不就是二分图最小点覆盖问题吗？

而最小点覆盖等于最大匹配。所以只要对这个图求一次最大匹配即可。

于是就解决了。时间复杂度 $O(n^2\log^2n)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9,NN=751,MM=280876;
int n,m,a[NN],cx[NN],cy[NN],vis[NN];
int head[NN],nxt[MM<<1],to[MM<<1],cnt=1;
bool cmp(int a,int b)
{int x=a&1,y=b&1;if(x!=y) return x<y;return a>b;
}
void add(int u,int v)
{to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
}
bool dfs(int u)
{for(int i=head[u];i;i=nxt[i]){if(!vis[to[i]]){vis[to[i]]=1;if(!cy[to[i]]||dfs(cy[to[i]])){cx[u]=to[i];cy[to[i]]=u;return 1;}}}return 0;
}
int match(int n)
{int ans=0;memset(cx,0,sizeof(cx));memset(cy,0,sizeof(cy));for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(!cx[i]) ans+=dfs(i);}return ans;
}
ll ksm(ll a,ll b,ll mod)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
int test[]={2,7,61};
bool check(ll a,ll x)
{ll czn=x-1;if(ksm(a,czn,x)!=1) return 0;do{ll xx=ksm(a,czn/2,x);if(xx!=1&&xx!=x-1) return 0;czn>>=1;}while(czn%2==0&&ksm(a,czn,x)==1);return 1;
}
bool miller_rabbin(ll x)
{if(x==1) return 0;if(x==2||x==7||x==61) return 1;for(int i=0;i<3;i++){if(!check(test[i],x))return 0;}return 1;
}
int main()
{freopen("cooking.in","r",stdin);freopen("cooking.out","w",stdout);int t;cin>>t;while(t--){cnt=0;memset(head,0,sizeof(head));memset(nxt,0,sizeof(nxt));scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+1+n,cmp);int l=1;while(a[l]%2==0) l++;while(a[n-1]==1) n--;for(int i=1;i<l;i++){for(int j=l;j<=n;j++){if(miller_rabbin(a[i]+a[j])){add(i,j),add(j,i);}}}cout<<n-match(l-1)<<endl;}
}