题目：http://acm.hdu.edu.cn/showproblem.php?pid=5594
完全不会啊TAT。。
其实官方题解已经说的很清楚了。。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <cstdlib> #include <queue> #include <cmath> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 405 #define ll long long #define inf int(1e9) using namespace std; int a[maxn],head[maxn],cur[maxn],uu[maxn],odd[maxn],even[maxn]; int tot,t,s; struct data{int obj,pre,c; }e[200500]; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } void insert(int x,int y,int z){ e[++tot].obj=y; e[tot].c=z; e[tot].pre=head[x]; head[x]=tot; e[++tot].obj=x; e[tot].c=0; e[tot].pre=head[y]; head[y]=tot; } bool bfs(){ queue<int >q; clr(uu,-1); uu[s]=0; q.push(s); while (!q.empty()){ int u=q.front(); q.pop(); for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; if (uu[v]==-1&&e[j].c) uu[v]=uu[u]+1,q.push(v); } } if (uu[t]==-1) return 0; return 1; } int dfs(int x,int mx){ if (x==t) return mx; int used=0; for (int j=cur[x];j;j=e[j].pre){ int v=e[j].obj; if (uu[v]==uu[x]+1){ int w=dfs(v,min(e[j].c,mx-used)); used+=w; e[j].c-=w; e[j^1].c+=w; if (e[j].c) cur[x]=j; if (used==mx) return mx; } } if (!used) uu[x]=-1; return used; } int dinic(){ int ans=0; while (bfs()){ rep(i,s,t) cur[i]=head[i]; ans+=dfs(s,inf); } return ans; } bool jud(int x){ int s=int(sqrt(x))+1; rep(i,2,s) if (x%i==0) return 0; return 1; } bool work(){ tot=1; clr(head,0); clr(odd,0); clr(even,0); //clr(one,0); int odd_cnt=0,even_cnt=0,one_in=0,one_out=0,one_cnt=0; int n=read(); rep(i,1,n) { a[i]=read(); if (a[i]>1&&(a[i]&1)) odd[++odd_cnt]=a[i]; else if (a[i]>1&&((a[i]&1)==0)) even[++even_cnt]=a[i]; else one_cnt++; } int need=even_cnt-odd_cnt; rep(i,1,one_cnt){ if (need) { one_in++; odd[++odd_cnt]=1; need--; } else one_out++; } if ((!one_in && (one_out==2||one_out==1)) || need!=0) return 0; s=0; t=2*odd_cnt+1; int cnt=odd_cnt; rep(i,1,cnt) insert(s,i,2); rep(i,1,cnt) insert(i+cnt,t,2); rep(i,1,cnt) rep(j,1,cnt){ if (jud(odd[i]+even[j])) { if (odd[i]==1&&one_out>0) insert(i,j+cnt,2); else insert(i,j+cnt,1); } } if (dinic()!=2*cnt) return 0; return 1; } int main(){ int T=read(); while (T--){ if (work()) puts("YES"); else puts("NO"); } return 0; }