题解 P5771 【[JSOI2016]反质数序列】

· · 题解

直接求不好求,但是容易发现这大概是一个二分图

因为同奇偶性的相加一定不是质数,不同奇偶性数相加就不一定了

所以按照奇偶构建二分图

奇数放二分图左边,偶数放二分图右边

若左边的i和右边的j满足a[i]+a[j]是质数则i向j连一条边

那么这样连边这样可以求一个最大匹配.....然而有啥用呢.....

最大匹配=最小点覆盖

最大独立集=点数-最小点覆盖

把最小点覆盖抽出来,剩下的数就是最大独立集,彼此不会形成质数

值得一提的是,1是特殊的数,因为1+1竟然是质数!!!

那么最后答案中肯定最多只有1个1

把多余的1去掉,就是名副其实的二分图了

<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
const int inf=1e9;
int n,m,s,t,dis[maxn],a[maxn];
struct edge{
    int to,nxt,flow;
}d[maxn]; int head[maxn],cnt=1;
int prime[maxn],vis[maxn],top;
void make_prime()
{
    vis[1]=1;
    for(int i=2;i<=2e5;i++)
    {
        if( !vis[i] )   prime[++top]=i;
        for(int j=1;j<=top&&i*prime[j]<=2e5;j++ )
        {
            vis[i*prime[j]]=1;
            if( i%prime[j]==0 ) break;
        }
    }
}
void add(int u,int v,int flow){
    d[++cnt]=(edge){v,head[u],flow},head[u]=cnt;
    d[++cnt]=(edge){u,head[v],0},head[v]=cnt;
}
bool bfs()
{
    for(int i=1;i<=t;i++)   dis[i]=0;
    dis[s]=1;
    queue<int>q; q.push( s );
    while( !q.empty() )
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=d[i].nxt )
        {
            int v=d[i].to;
            if( d[i].flow&&dis[v]==0 )
            {
                dis[v]=dis[u]+1;
                if( v==t )  return true;
                q.push( v );
            }
        }
    }
    return false;
}
int dinic(int u,int flow)
{
    if( u==t )  return flow;
    int res=flow;
    for(int i=head[u];i&&res;i=d[i].nxt )
    {
        int v=d[i].to;
        if( dis[v]==dis[u]+1&&d[i].flow)
        {
            int temp=dinic(v,min(res,d[i].flow) );
            if( temp==0 )   dis[v]=0;
            res-=temp;
            d[i].flow-=temp;
            d[i^1].flow+=temp;
        }
    }
    return flow-res;
}
int main()
{
    make_prime();
    cin >> n;
    s=0,t=n+1; 
    int one=0,sumn=n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        if( a[i]==1 )
        {
            one++;
            if( one>1 )
            {
                a[i]=-1,sumn--;
                continue;
            }
        }
        if( a[i]%2==1 ) add(s,i,1);
        else    add(i,t,1);
    }
    for(int i=1;i<=n;i++)
    {
        if( a[i]%2==0||a[i]==-1 )   continue;
        for(int j=1;j<=n;j++)
        {
            if( a[j]==-1||a[j]%2==1 )   continue;
            if( !vis[a[i]+a[j]] )
                add(i,j,1);
        }
    }
    int ans=0;
    while( bfs() )  ans+=dinic(s,inf);
    int k=max(0,one-1);
    cout << n-k-ans;
}