本文主要是介绍素数伴侣--最大二分匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<bits/stdc++.h>
using namespace std;
#define N 100
int edge[N][N],cx[N],cy[N];//edge记录两点的关系，如果两点相连，则edge【i】【j】为1
int visited[N];//判断该店是否被访问过
int nx,ny,res;
const int M=60000+100;
bool prim[M];
void initprim()
{memset(prim,true,sizeof(prim));prim[0]=prim[1]=false;for(int i=2; i*i<=M; i++)for(int j=i*i; j<M; j+=i){if(prim[j])prim[j]=false;}
}
int path(int u)
{int v;for(v=0; v<ny; v++){if(edge[u][v]&&!visited[v]){visited[v]=1;if(cy[v]==-1||path(cy[v]))如果y集合中的v元素没有匹配或者是v已经匹配，但是从cy[v]中能够找到一条增广路{cx[u]=v;cy[v]=u;return 1;}}}return 0;
}
int main()
{int n;initprim();while(scanf("%d",&n)!=EOF){int i,j,a[100]= {0},a1[100]= {0},a2[100]= {0};nx=0,ny=0,res=0;memset(cx,0xff,sizeof(cx));memset(cy,0xff,sizeof(cy));//初始值为-1表示两个集合中都没有匹配的元素！memset(edge,0,sizeof(edge));for(i=0; i<n; i++){scanf("%d",&a[i]);if(a[i]%2==1)a1[nx++]=a[i];elsea2[ny++]=a[i];}for(i=0; i<nx; i++) //初始化edge数组，如果两个数之和为素数，则edge[i][j]置1{for(j=0; j<ny; j++){if(prim[a1[i]+a2[j]])edge[i][j]=1;}}for(i=0; i<nx; i++){if(cx[i]==-1){memset(visited,0,sizeof(visited));res+=path(i);}}printf("%d\n",res);}
}
这篇关于素数伴侣--最大二分匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
