题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
输出:
输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
输入说明
1 输入一个正偶数 n
2 输入 n 个整数
求得的“最佳方案”组成“素数伴侣”的对数。
4 2 5 6 13
2
2 3 6
0
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <limits.h> #include <math.h> #include <algorithm> #include <vector> using namespace std; vector<int> G[105]; bool flag[105]; int pre[105]; bool dfs(int k){ int x; for(int i=0;i<G[k].size();i++){ x=G[k][i]; if (flag[x]) continue; flag[x]=true; if((pre[x]==0)||dfs(pre[x])){ pre[x]=k; return true; } } return false; } bool isprime[80000]; int nums[105]; int main(){ memset(isprime,1,sizeof(isprime)); isprime[0]=isprime[1]=false; for(int i=4;i<80000;i+=2)isprime[i]=false; for(int i=3;i*i<80000;i+=2) if(isprime[i]){ for(int j=i*i;j<80000;j+=2*i) isprime[j]=false; } int n; while(~scanf("%d",&n)){ for(int i=1;i<=n;i++){ scanf("%d",&nums[i]); } for(int i=1;i<=n;++i){ for(int j=i+1;j<=n;++j){ if(isprime[nums[i]+nums[j]]){ (nums[i]&1)?G[i].push_back(j):G[j].push_back(i); } } } memset(pre,0,sizeof(pre)); int ans=0; for(int i=1;i<=n;i++){ memset(flag,false,sizeof(flag)); if (dfs(i)) ans++; } printf("%d\n",ans); for(int i=1;i<=n;++i){ G[i].clear(); } } return 0; }#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N=510; int n,m,x,y;vector<int>g[N]; namespace Blossom{ int mate[N],n,ret,nxt[N],f[N],mark[N],vis[N];queue<int>Q; int F(int x){return x==f[x]?x:f[x]=F(f[x]);} void merge(int a, int b){f[F(a)]=F(b);} int lca(int x, int y){ static int t=0;t++; for(;;swap(x,y)) if(~x){ if(vis[x=F(x)]==t) return x;vis[x]=t; x=mate[x]!=-1?nxt[mate[x]]:-1; } } void group(int a, int p){ for(int b,c;a!=p;merge(a,b),merge(b,c),a=c){ b=mate[a],c=nxt[b]; if(F(c)!=p)nxt[c]=b; if(mark[b]==2)mark[b]=1,Q.push(b); if(mark[c]==2)mark[c]=1,Q.push(c); } } void aug(int s, const vector<int>G[]){ for(int i=0;i<n;++i)nxt[i]=vis[i]=-1,f[i]=i,mark[i]=0; while(!Q.empty())Q.pop();Q.push(s);mark[s]=1; while(mate[s]==-1&&!Q.empty()){ int x=Q.front();Q.pop(); for(int i=0,y;i<(int)G[x].size();++i){ if((y=G[x][i])!=mate[x]&&F(x)!=F(y)&&mark[y]!=2){ if(mark[y]==1){ int p=lca(x,y); if(F(x)!=p)nxt[x]=y; if(F(y)!=p)nxt[y]=x; group(x,p),group(y,p); }else if(mate[y]==-1){ nxt[y]=x; for(int j=y,k,l;~j;j=l)k=nxt[j],l=mate[k],mate[j]=k,mate[k]=j; break; }else nxt[y]=x,Q.push(mate[y]),mark[mate[y]]=1,mark[y]=2; } } } } int solve(int _n, const vector<int>G[]){ n=_n;memset(mate, -1, sizeof mate); for(int i=0;i<n;++i) if(mate[i]==-1)aug(i,G); for(int i=ret=0;i<n;++i)ret+=mate[i]>i; printf("%d\n",ret); //for(int i=0;i<n;i++)printf("%d %d\n",i+1,mate[i]+1); return ret; } } bool isprime[80000]; int nums[105]; int main(){ memset(isprime,1,sizeof(isprime)); isprime[0]=isprime[1]=false; for(int i=4;i<80000;i+=2)isprime[i]=false; for(int i=3;i*i<80000;i+=2) if(isprime[i]){ for(int j=i*i;j<80000;j+=2*i) isprime[j]=false; } while(~scanf("%d",&n)){ for(int i=0;i<n;i++){ scanf("%d",&nums[i]); } for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ if(isprime[nums[i]+nums[j]]){ g[i].push_back(j); g[j].push_back(i); } } } Blossom::solve(n,g); for(int i=0;i<n;++i){ g[i].clear(); } } }