题解

分析

因为只有奇数和偶数配对才有可能得出质数，

暴力求出每一对\(a_i+a_j\)为质数，将其中的奇数想偶数连一条边。

二分图匹配，匈牙利算法。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=45;

using namespace std;

int n,a[N],pt[N*N],used[N*N],b[N][N],ans;

int find(int x)

{

	if(used[x]) return 0;

	used[x]=1;

	for(int i=1;i<=b[x][0];i++)

	{

		if(pt[b[x][i]]==0 || find(pt[b[x][i]]))

		{

			pt[b[x][i]]=x;

			return 1;

		}

	}

	return 0;

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&a[i]);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			if(i!=j)

			{

				bool q=true;

				for(int k=2;k<=sqrt(a[i]+a[j])+1 && q;k++)

				{

					if((a[i]+a[j])%k==0) q=false;

				}

				if(q) b[i][++b[i][0]]=j;

			}

	for(int i=1;i<=n;i++)

		if(a[i]%2)

		{

			memset(used,0,sizeof(used));

			ans+=find(i);

		}

	cout<<ans<<endl;

}

巴特西

【NOIP2016提高A组集训第3场10.31】高维宇宙

题解

分析

最新文章

热门文章