题目描述若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
输入:
有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。
输出:
输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数。
输入说明1 输入一个正偶数n2 输入n个整数
求得的“最佳方案”组成“素数伴侣”的对数。
本身没啥难度,明显的二部图算法.值得一提的是,这里要注意使用线性筛法求素数,加快时间;同时可以用Vector来存储数据(因为不知道输入数据规模),然后判断奇偶性,不用使用两个数组来存储,节省空间.最后,while(scanf() != EOF)这里,我忘了写 !=EOF,害的交上去一直运行超时,我想了好久的优化……最后发现原来是自己傻了,漏写东西了.还是学艺不精啊……
/* 素数伴侣 二部图算法，将奇数和偶数分为两个部分，加起来的和为素数的算是匹配成功，求最大匹配。 */ #include <iostream> #include <string.h> #include <stdio.h> #include <math.h> using namespace std; int N, res; int Ji[101] = {}, Ou[101] = {}; int Numji = 0, Numou = 0, t = 0; int map[110][110];//记录能否配对 bool prime[60010];//素数表 bool flag[100000]; int vis[110], mat[110]; void Is()//筛法求素数 { //memset(flag,true,sizeof(flag)); for(int i=2;i<=60010;i++) { if(flag[i] == 0) { for(int j=i<<1;j<=60010;j+=i) flag[j] = 1;//它的倍数求全不是素数 } } for(int i=2;i<=60010;i++) if(flag[i] == 0) prime[i] = 1;//打表 } bool Find(int x) { for(int i=1;i<=Numou;i++) if(!vis[i] && prime[Ji[x]+Ou[i]]==1) { vis[i] = 1; if(!mat[i] || Find(mat[i])) { mat[i] = x; return true; } } return false; } void hungary() { for(int i=1;i<=Numji;i++) { memset(vis,0,sizeof(vis)); if(Find(i)) res += 1; } } int main() { Is();//打表 while(scanf("%d",&N) != EOF)//一定要加 EOF，不然超时.......为此想了好久优化不得其解 QAQ { Numji = 1; Numou = 1; res = 0;//从 1 开始计数 //memset(map,0,sizeof(map)); //memset(vis,0,sizeof(vis)); memset(mat,0,sizeof(mat)); for(int i=0;i<N;i++) { scanf("%d",&t); if(t%2)//奇数 Ji[Numji++] = t; else Ou[Numou++] = t; } Numji -= 1; Numou -= 1; hungary(); printf("%d\n",res); //cout<<prime[N]<<endl; } return 0; }