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
2
7
3 4 8 9 1 1 1
3
1 2 3
Sample Output
YES
NO
HINT
题意
题解：
代码：
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cstring>
using namespace std; namespace NetFlow
{
const int MAXN=,MAXM=,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=; memset(G,-,sizeof(G[])*N);
}
void link(int u,int v,int c)
{
E[sz]=Edge(v,c,,G[u]); G[u]=sz++;
E[sz]=Edge(u,,,G[v]); G[v]=sz++;
}
int ISAP(int S,int T)
{//S -> T
int maxflow=,aug=inf,flag=false,u,v;
for (int i=;i<N;++i)cur[i]=G[i],gap[i]=dis[i]=;
for (gap[S]=N,u=pre[S]=S;dis[S]<N;flag=false)
{
for (int &it=cur[u];~it;it=E[it].nx)
{
if (E[it].c>E[it].f&&dis[u]==dis[v=E[it].v]+)
{
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]^].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]<mx)
{
mx=dis[E[it].v]; cur[u]=it;
}
}
if ((--gap[dis[u]])==) break;
++gap[dis[u]=mx+]; u=pre[u];
}
return maxflow;
}
bool bfs(int S,int T)
{
static int Q[MAXN]; memset(dis,-,sizeof(dis[])*N);
dis[S]=; Q[]=S;
for (int h=,t=,u,v,it;h<t;++h)
{
for (u=Q[h],it=G[u];~it;it=E[it].nx)
{
if (dis[v=E[it].v]==-&&E[it].c>E[it].f)
{
dis[v]=dis[u]+; Q[t++]=v;
}
}
}
return dis[T]!=-;
}
int dfs(int u,int T,int low)
{
if (u==T) return low;
int ret=,tmp,v;
for (int &it=cur[u];~it&&ret<low;it=E[it].nx)
{
if (dis[v=E[it].v]==dis[u]+&&E[it].c>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^].f-=tmp;
}
}
}
if (!ret) dis[u]=-; return ret;
}
int dinic(int S,int T)
{
int maxflow=,tmp;
while (bfs(S,T))
{
memcpy(cur,G,sizeof(G[])*N);
while (tmp=dfs(S,T,inf)) maxflow+=tmp;
}
return maxflow;
}
}
using namespace NetFlow; int One;
vector<int> Even,Odd;
const int MAXN_ = ;
bool _flag[MAXN_];
int _primes[MAXN_], _pi;
void GetPrime_1()
{
int i, j;
_pi = ;
memset(_flag, false, sizeof(_flag));
for (i = ; i < MAXN_; i++)
if (!_flag[i])
{
_primes[i] = ;//素数标识为1
for (j = i; j < MAXN_; j += i)
_flag[j] = true;
}
}
void Clear()
{
Even.clear();
Odd.clear();
init();
One=;
}
bool work()
{
int n;scanf("%d",&n);
int flag = ;
for(int i=;i<=n;i++)
{
int x;scanf("%d",&x);
if(x==)One++;
else if(x%==)Odd.push_back(x);
else Even.push_back(x);
}
if(Odd.size()>Even.size())return ;
if(Odd.size()+One<Even.size())return ;
int In = ;
while(Odd.size()<Even.size())
{
flag = ;
Odd.push_back();
One--;
In++;
}
if(flag==&&(One==||One==))return ;
int tmp = ;
for(int i=;i<Odd.size();i++)
link(,+i,);
for(int i=;i<Even.size();i++)
link(n++i,,);
for(int i=;i<Odd.size();i++)
{
for(int j=;j<Even.size();j++)
{
if(_primes[Odd[i]+Even[j]])
{
if(Odd[i]==&&One>&&In>)
link(+i,n++j,);
else
link(+i,n++j,);
}
}
}
if(Even.size()*==dinic(,))return ;
return ;
}
int main()
{
GetPrime_1();
int t;
scanf("%d",&t);
for(int cas=;cas<=t;cas++)
{
Clear();
printf("%s\n",work()?"YES":"NO");
}
}