二分图的概念：二分图是图中的特殊模型，图的顶点v可以划分为互不相交的两个子集(a，b )，且与图中各边(I，j )相关的两个顶点I和j分别为这两个不同的顶点集合(i in A，j in B )
二分图如下。
本文用一个问题引出二分图的最大匹配算法。 以质数伴侣的主题为例。 假设两个正整数之和是素数，则这两个数称为素数伙伴。 设计程序从现有的n个正整数中选择几个对数构成素数伙伴，可以选择多少对？
分析：偶数除2外不是素数，两个偶数之和和两个奇数之和均为偶数。 只有奇数和偶数可以做素数的伴侣。 为了解决这个问题，把奇数分为一种，偶数分为一种，两种中元素之和为素数的话，在两种之间连接线，解决这个问题需要寻求最多的连接组合。 两种元素被认为是二分图，使用匈牙利算法可以很好地解决这个问题。
以下介绍匈牙利算法，但在介绍匈牙利算法之前，必须了解扩展路、匹配边、未匹配边、匹配点、未匹配点的概念。 匹配边是指在二分图中连接两个点集的边，匹配边的两端是赛点。 不一致的边缘是二分图中连接两个点集之间的边缘，不一致的边缘的一端不一致的点的一端一致。 增广路是指在二分图中从未匹配点开始，以未匹配边、匹配边交替的模式找到未匹配点后结束。 在这里仔细想想。 找到失配点意味着什么？
走在扩大路上找到未匹配点后，断开扩大路中的匹配边。 第一个重合点和第一个重合点形成重合边。 第二个匹配点和最后一个未匹配点构成第二个匹配边。 意味着找到了匹配的边缘。
下图：
图中1-4之间的边是匹配边，顶点是赛点。 2-5之间的变化是匹配边，顶点是赛点。 我们现在没有从匹配点找扩大路。 从顶点3出发，按照未匹配边、匹配边的模式查找扩大路。 在3-4不匹配的边缘、4-1匹配的边缘、1-5不匹配的边缘、5-2匹配的边缘、2-6不匹配的边缘、6不匹配的点上，找到加宽路线。 如果断开匹配的边，则可以看到与图匹配的边增加了一条，如下所示：
上图完成了二分图的最大匹配。
为了解决素数伴侣的问题，首先，输入的奇数被分类为奇数编号，而可以构成素数伴侣的奇偶校验数量被设置为偶数存储在二维阵列中并且偶数的行为匹配的奇数。 也就是说，与一个奇数匹配并且形成素数的伙伴的所有偶数都被放置在与二维阵列的该奇数对应的行中。 下图：
1奇数火柴2、4、6； 奇数匹配4、6； 奇数5等于2，4。
在二维阵列中查找扩展路径：
初始化素数伴侣对数，设置匹配素数伴侣中偶数的第一个奇数伴侣的数组pre为0，而如果pre[j]=1，则指示匹配偶数j的第一个奇数为1。 用于初始化素数伙伴的标志位used阵列为0，used[i]=1指示偶数I已经被用于与其他奇数构成伙伴。
进入循环，用匈牙利算法查找扩大路，如果找到扩大路，将计数值加1。
接下来介绍匈牙利的算法。 代码如下。
//匈牙利算法boolDFS(intk ) { for } inti=0； iG[k].size (； I () if ) used[g[k][I]==0) { used[G[k][i]]=1； if (pre [ g [ k ] [ I ]==0||DFS (pre [ g ] [ I ] ) ) { pre[G[k][i]]=k； 返回真； } } else continue； }返回假； //匹配规则memset(pre，0，sizeof ) )； int count=0； for(intI=1； i=N； I )消息集(used，0，sizeof ) used )； if(DFS ) I ) ) count； }根据上述矩阵说明匈牙利算法，是匈牙利算法中的第一个
先used[G[1][1]]=used[2]=0使其置1表示偶数2已经被使用与其他奇数构成了伴侣。pre[G[1][1]]=0表示还没有与偶数2匹配的奇数，程序继续执行将pre[G[1][1]]=1表示与偶数2匹配的奇数为1。当执行到偶数行时直接跳过。当程序执行到矩阵的第5行要找与5匹配的偶数时，used[G[5][1]]=used[2]=0，程序将其置1表示偶数2已经被使用与奇数5构成了伴侣，pre[G[5][1]]=pre[2]=1发现偶数2之前与奇数1已经进行过一次匹配。然后程序进入dfs(pre[G[5][1]])=dfs(1)，再重新对1寻求未匹配的偶数然后找到偶数4，发现偶数4之前与奇数3进行过匹配，则进而对奇数3再寻找未匹配的偶数，找到偶数6，发现pre[G[3][2]]=0表示还没有与偶数6匹配的奇数，则找到一个未匹配的点偶数6，进而找到一条增广路则计数值加1。整理一下思路，当程序执行到矩阵的第5行要找与5匹配的偶数时，从未匹配点5开始经过未匹配边5-2，匹配边2-1，未匹配边1-4，匹配边4-3，未匹配边3-6，找到未匹配点6.找到一条增广路。对其所有顶点就行循环则完成了二分图的最大匹配，也解决了素数伴侣问题。
整体代码如下：
#include <iostream>#include <cstring>#include <vector>using namespace std;vector<int> G[105];int pre[105];bool used[105];bool dfs(int k){ for(int i=0;i<G[k].size();++i) { if(used[G[k][i]] == 0) { used[G[k][i]] = 1; if(pre[G[k][i]] == 0 || dfs(pre[G[k][i]])) { pre[G[k][i]]=k; return true; } } else continue; } return false;}int main(){ bool isprime[60000]; memset(isprime,1,sizeof(isprime)); isprime[0]=0;//数据从2开始的 isprime[1]=0; for(int i=4;i<60000;i+=2)//除了2以外所有的偶数都不是质数 isprime[i]=0; for(int i=3;i*i<60000;i+=2) if(isprime[i]) for(int j=i*i;j<60000;j+=2*i)//任意两个奇数的乘积都不是素数 isprime[j]=0; int N; int nums[105]; int temp; while(cin>>N) { for(int i=1;i<=N;++i) { cin>>temp; nums[i]=temp; } //匹配规则 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 count=0; for(int i=1;i<=N;++i) { memset(used,0,sizeof(used)); if(dfs(i)) count++; } cout<<count<<endl; for(int i=1;i<=N;++i) G[i].clear(); } return 0;}