题解 P5771【 [JSOI2016]反质数序列】
crescentic · · 题解
题目链接
可以看出是道二分图最大独立集。
题目分析：
分析可得：
- 当两个数奇偶性相同时，肯定满足条件（和为偶数）
所以，源点连向偶数，奇数连向汇点（其实交换源汇点也可以，看心情叭）。如果两数之和为质数，就在他们之间连边。最后
注意点：
- 边权均为
1 ：所求答案为选择的数量； - 需要判断
1 出现的次数：两个1 相加还是质数， 直接删去一个1 就好了，不会影响结果。 - 两个数连边时，注意源点和汇点的奇偶顺序，提前判断枚举的节点的奇偶正确性。
完整代码：
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define rt register int
#define int long long
const int N = 6010, M = 2e6,inf = 2e9,maxn = 2e5;
int n,m,S,T,tot = 1,a[N],head[N],cur[N],dep[N],f[M],prime[maxn],cnt;
bool vis[maxn + 10],tru[maxn + 10];
struct node {
int to,nex;
}e[M];
inline void add(int x,int y,int w) {
e[++tot] = (node) {y,head[x]}, f[tot] = w, head[x] = tot;
e[++tot] = (node) {x,head[y]}, head[y] = tot;
}
inline void read(int &x) {
x = 0;
int ff = 1; char s = getchar();
while(s < '0' || s > '9') {s = getchar();}
while(s <= '9' && s >= '0') { x = x * 10 + s - '0'; s = getchar();}
x *= ff;
}
inline bool bfs() {
memset(dep,-1,sizeof(dep));
dep[S] = 0, cur[S] = head[S];
queue<int> q;
q.push(S);
int now,ver;
while(!q.empty()) {
now = q.front();
q.pop();
for(rt i = head[now]; i; i = e[i].nex) {
ver = e[i].to;
if(dep[ver] == -1 && f[i]) {
dep[ver] = dep[now] + 1, cur[ver] = head[ver];
if(ver == T) return 1;
q.push(ver);
}
}
}
return 0;
}
inline int find(int x,int limit) {
if(x == T) return limit;
int ver,flow = 0,tmp;
for(rt i = cur[x]; i && flow < limit; i = e[i].nex) {
cur[x] = i, ver = e[i].to;
if(dep[ver] == dep[x] + 1 && f[i]) {
tmp = find(ver,min(limit - flow,f[i]));
if(!tmp) dep[ver] = -1;
f[i] -= tmp, f[i ^ 1] += tmp, flow += tmp;
}
}
return flow;
}
inline int dinic() {
int res = 0,flow;
while(bfs()) while(flow = find(S,inf)) res += flow;
return res;
}
inline void init() {//预处理质数
for(rt i = 2; i <= maxn; i ++) {
if(!vis[i]) {
prime[++cnt] = i;
tru[i] = 1;
}
for(rt j = 1; j <= cnt && i *prime[j] <= maxn; j ++) {
vis[i *prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
signed main() {
init();
read(n);
S = n + 1, T = S + 1;
int u,flag = 0,ans;
for(rt i = 1; i <= n; i ++) {
read(a[i]);
if(a[i] == 1 && flag) {//如果出现2个及以上的1，直接删除
n --, i --;
continue;
}
if(a[i] == 1) flag = 1;
if(a[i] & 1) add(i,T,1);
else add(S,i,1);
}
for(rt i = 1; i <= n; i ++) {
if(a[i] & 1) continue; //与源点相连的应该是偶数，奇数跳过
for(rt j = 1; j <= n; j ++) {
if(a[j] % 2 == 0) continue;//参考上文
if(tru[a[i] + a[j]]) add(i,j,1);
}
}
ans = n;
printf("%lld",ans - dinic());
return 0;
}