IV.[JSOI2016]反质数序列
神题……想了一下午才想出来……
同前几题一样，我们可以提出所有和为质数的对，然后跑二分图最大独立集。
先证明一下它为什么是二分图：我们可以令所有奇数为左部，所有偶数为右部。则所有同部间的对的和都是偶数（奇+奇=偶，偶+偶=偶）。则它是一个二分图。
等等，我们好像没有考虑\(1\)！有\(1+1=2\)，它们尽管在同一部，但和却是一个质数。
这里我的想法就比较naive了：首先强制选择一个\(1\)，在删去所有与\(1\)的和为质数的数后的图上跑独立集。这种方案的答案为（独立集大小\(+1\)）（这个\(1\)是强制选的那个\(1\)）。
而第二种做法是强制不选\(1\)，这种方案的答案为（独立集大小）。
然后最终答案即为两种方案的\(\max\)。
这种naive的想法固然可行，但是，看了题解后，我发现了更简单的做法：对于重复的\(1\)，只考虑1次（你不能同时选上两个\(1\)）。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,num[3010],one,head[3010],cnt,cur[3010],dep[3010],res,S,T,ans;
bool prime[200100];
bool PRIME(int ip){
if(ip<2)return false;
for(int i=2;i*i<=ip;i++)if(!(ip%i))return false;
return true;
}
struct node{
int to,next,val;
}edge[4001000];
void ae(int u,int v,int w){
// printf("(%d,%d)\n",u,v);
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
}
queue<int>q;
inline bool bfs(){
memset(dep,0,sizeof(dep)),q.push(S),dep[S]=1;
while(!q.empty()){
register int x=q.front();q.pop();
for(register int i=cur[x]=head[x];i!=-1;i=edge[i].next)if(edge[i].val&&!dep[edge[i].to])dep[edge[i].to]=dep[x]+1,q.push(edge[i].to);
}
return dep[T]>0;
}
bool reach;
inline int dfs(int x,int flow){
if(x==T){
res+=flow;
reach=true;
return flow;
}
int used=0;
for(register int &i=cur[x];i!=-1;i=edge[i].next){
if(!edge[i].val||dep[edge[i].to]!=dep[x]+1)continue;
register int ff=dfs(edge[i].to,min(edge[i].val,flow-used));
if(ff){
edge[i].val-=ff;
edge[i^1].val+=ff;
used+=ff;
if(used==flow)break;
}
}
return used;
}
inline void Dinic(){
while(bfs()){
reach=true;
while(reach)reach=false,dfs(S,0x3f3f3f3f);
}
}
int main(){
for(int i=1;i<=200000;i++)prime[i]=PRIME(i);
scanf("%d",&n),S=n+1,T=n+2;
for(int i=1;i<=n;i++)scanf("%d",&num[i]),one+=(num[i]==1);
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++){
if(num[i]==1)continue;
if(prime[num[i]+1])continue;
ans++;
if(num[i]&1)ae(S,i,1);
else ae(i,T,1);
for(int j=i+1;j<=n;j++){
if(num[j]==1)continue;
if(prime[num[j]+1])continue;
if(!prime[num[i]+num[j]])continue;
if(num[i]&1)ae(i,j,1);
else ae(j,i,1);
}
}
Dinic();
ans=ans-res;
if(one)ans++;
for(int i=1;i<=n;i++){
if(num[i]==1)continue;
if(prime[num[i]+1]){
if(num[i]&1)ae(S,i,1);
else ae(i,T,1);
}
for(int j=i+1;j<=n;j++){
if(num[j]==1)continue;
if(!prime[num[i]+1]&&!prime[num[j]+1])continue;
if(!prime[num[i]+num[j]])continue;
if(num[i]&1)ae(i,j,1);
else ae(j,i,1);
}
}
Dinic();
ans=max(ans,n-one-res);
printf("%d\n",ans);
return 0;
}