[JZOJ 4832]高维宇宙

Description Input Sample Input 5 2 9 11 12 37 Output Sample Output 2

The Solution

其实这道题题目大意简化一下就是 将第I个数看成编号为I的一个点 若 ai+aj 为质数，则点I与点j之间连一条无向边 然后染色跑一遍二分图匹配就好了

CODE

#include <cstdio> #include <algorithm> #include <cstring> #define fo(i,a,b) for (int i=a;i<=b;i++) #define N 45 * 45 #define M 2005 using namespace std; int a[45],Prime[2000],Final[N],Color[N],Vis[N]; int cnt = 0,n,tot = 0,ans = 0; bool bz[N],Mark[N]; struct node { int to,next; node(void){} node(int a,int b) : to(a),next(b){} }e[N * 2]; void Link(int u,int v) { e[++ tot] = node(v,Final[u]),Final[u] = tot; e[++ tot] = node(u,Final[v]),Final[v] = tot; } void Pretreatment() { fo(i,2,2000) { if (!bz[i]) Prime[++ cnt] = i; int j = 1; while (Prime[j] * i <= 2000 && j <= cnt) { bz[i * Prime[j]] = true; if (i % Prime[j] == 0) break; j++; } } } void dfs(int x) { for (int i = Final[x];i;i = e[i].next) { int t = e[i].to; if (Color[t] == -1) { Color[t] = Color[x] ^ 1; dfs(t); } } } int Hungarian(int x) { for (int i = Final[x];i;i = e[i].next) { int t = e[i].to; if (!Mark[t]) { Mark[t] = true; if (!Vis[t] || Hungarian(Vis[t])) { Vis[t] = x; return true; } } } return false; } int main() { freopen("prime.in","r",stdin); freopen("prime.out","w",stdout); scanf("%d",&n); fo(i,1,n) scanf("%d",&a[i]); Pretreatment(); memset(Color,255,sizeof(Color)); fo(i,1,n-1) fo(j,i+1,n) if (!bz[a[i] + a[j]]) Link(i,j); fo(i,1,n) if (Color[i] == -1) Color[i] = 0,dfs(i); fo(i,1,n) if (Color[i] == 0) { memset(Mark,false,sizeof(Mark)); if (Hungarian(i)) ans ++; } printf("%d\n",ans); return 0; }