题目描述

数据范围

解法

由于大于4的素数只有可能由奇数和偶数的和得出。

所以根据数的奇偶性可以分出两类数奇数和偶数。

奇数之间不会相互匹配，偶数之间也不会相互匹配。

那么原问题转化为二分图最大匹配。

网络流即可。

代码

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

const char* fin="prime.in";

const char* fout="prime.out";

const int inf=0x7fffffff;

const int maxn=207,maxa=2007;

int n,i,j,k,ans=0,en,ls,rs;

int a[maxn],c[maxa];

int b[maxn];

int tot=1,fi[maxn],la[maxa],va[maxa],ne[maxa],cnt[maxn],bz[maxn];

int gg(int x){

    return 1+x;

}

void add_line(int a,int b,int c){

    tot++;

    ne[tot]=fi[a];

    la[tot]=b;

    va[tot]=c;

    fi[a]=tot;

}

void add(int a,int b){

    add_line(a,b,1);

    add_line(b,a,0);

}

int gap(int v,int flow){

    int i,use=0,k;

    if (v==en) return flow;

    for (k=fi[v];k;k=ne[k])

        if (bz[v]==bz[la[k]]+1 && va[k]){

            i=gap(la[k],min(flow-use,va[k]));

            use+=i;

            va[k]-=i;

            va[k^1]+=i;

            if (use==flow || bz[1]==en) return use;

        }

    if (!--cnt[bz[v]]) bz[1]=en;

    cnt[++bz[v]]++;

    return use;

}

bool p[maxa];

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

    for (i=2;i<maxa;i++){

        if (!p[i]) c[++c[0]]=i;

        for (j=1;j<=c[0];j++){

            if (i*c[j]>=maxa) break;

            p[i*c[j]]=true;

            if (i%c[j]==0) break;

        }

    }

    scanf("%d",&n);

    en=2+n;

    for (i=1;i<=n;i++){

        scanf("%d",&a[i]);

        if (a[i]%2) add(1,gg(i));

        else add(gg(i),en);

    }

    for (i=1;i<=n;i++) for (j=1;j<=n;j++)

        if (a[i]%2==1 && a[j]%2==0 && !p[a[i]+a[j]]) add(gg(i),gg(j));

    cnt[0]=en;

    while (bz[1]<en) ans+=gap(1,inf);

    printf("%d",ans);

    return 0;

}

启发

原本的想法就是网络流，但发现一次匹配会用去两个数的使用次数。

并没有注意到大于四的素数只能由偶数和奇数的和得到这个性质。

两两匹配问题考虑把原数集分为两个独立集。

这道题似乎还可以贪心，脑洞较小无法想出。

想点办法打开脑洞。