ZYB's Prime

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5594

Description

After getting 600 scores in NOIP,ZYB(ZJ−267) creates a problem:you are given N numbers,now you are asked to divide them into K groups（K≥1),the

number of each group must be no less than 3,and put all the numbers in a group into a ring,the sum of every two adjacent numbers must be a prime.ZYB want to ask

you whether the N numbers can be divided or not?

Input

In the first line there is the testcase T.

For each teatcase:

In the first line there is one number N.

In the next line there are N numbers Ai.

1≤T≤50,1≤N≤200,1≤Ai≤200,for 60% cases N≤20.

Output

For each testcase,print the YES or NO.

Sample Input

3 4 8 9 1 1 1

1 2 3

Sample Output

YES

HINT

题意

题解：

代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;namespace NetFlow{    const int MAXN=100000,MAXM=100000,inf=1e9;    struct Edge    {        int v,c,f,nx;        Edge() {}        Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {}    } E[MAXM];    int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],N,sz;    void init(int _n)    {        N=_n,sz=0; memset(G,-1,sizeof(G[0])*N);    }    void link(int u,int v,int c)    {        E[sz]=Edge(v,c,0,G[u]); G[u]=sz++;        E[sz]=Edge(u,0,0,G[v]); G[v]=sz++;    }    int ISAP(int S,int T)    {
    //S -> T        int maxflow=0,aug=inf,flag=false,u,v;        for (int i=0;i
         
          E[it].f&&dis[u]==dis[v=E[it].v]+1)                {                    if (aug>E[it].c-E[it].f) aug=E[it].c-E[it].f;                    pre[v]=u,u=v; flag=true;                    if (u==T)                    {                        for (maxflow+=aug;u!=S;)                        {                            E[cur[u=pre[u]]].f+=aug;                            E[cur[u]^1].f-=aug;                        }                        aug=inf;                    }                    break;                }            }            if (flag) continue;            int mx=N;            for (int it=G[u];~it;it=E[it].nx)            {                if (E[it].c>E[it].f&&dis[E[it].v]
          
           E[it].f) { dis[v]=dis[u]+1; Q[t++]=v; } } } return dis[T]!=-1; } int dfs(int u,int T,int low) { if (u==T) return low; int ret=0,tmp,v; for (int &it=cur[u];~it&&ret
           
            E[it].f) { if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f))) { ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp; } } } if (!ret) dis[u]=-1; return ret; } int dinic(int S,int T) { int maxflow=0,tmp; while (bfs(S,T)) { memcpy(cur,G,sizeof(G[0])*N); while (tmp=dfs(S,T,inf)) maxflow+=tmp; } return maxflow; }}using namespace NetFlow;int One;vector
            
              Even,Odd;const int MAXN_ = 10000;bool _flag[MAXN_];int _primes[MAXN_], _pi;void GetPrime_1(){ int i, j; _pi = 0; memset(_flag, false, sizeof(_flag)); for (i = 2; i < MAXN_; i++) if (!_flag[i]) { _primes[i] = 1;//素数标识为1 for (j = i; j < MAXN_; j += i) _flag[j] = true; }}void Clear(){ Even.clear(); Odd.clear(); init(100000); One=0;}bool work(){ int n;scanf("%d",&n); int flag = 0; for(int i=1;i<=n;i++) { int x;scanf("%d",&x); if(x==1)One++; else if(x%2==1)Odd.push_back(x); else Even.push_back(x); } if(Odd.size()>Even.size())return 0; if(Odd.size()+One
             
              0&&In>0) link(1+i,n+2+j,2); else link(1+i,n+2+j,1); } } } if(Even.size()*2==dinic(0,600))return 1; return 0;}int main(){ GetPrime_1(); int t; scanf("%d",&t); for(int cas=1;cas<=t;cas++) { Clear(); printf("%s\n",work()?"YES":"NO"); }}