题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如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
package main
import (
"fmt"
)
func isPrime(n int) bool {
if n < 2 {
return false
}
for i := 2; i*i <= n; i++ {
if n%i == 0 {
return false
}
}
return true
}
func getMax(nums []int) int {
res := 0
// 按奇偶划分
odds := []int{}
evens := []int{}
for i := 0; i < len(nums); i++ {
if nums[i]&1 == 1 {
odds = append(odds, nums[i])
} else {
evens = append(evens, nums[i])
}
}
n := len(evens)
// 为每个奇数寻找匹配的偶数
// 采用的策略：先到先得, 能让则让
// 先到先得：如果该偶数的匹配为0，就直接与之匹配
// 能让则让：如果该偶数已经匹配(匹配不为零)，那么为与之匹配的奇数重新寻找匹配，如果能找到新的匹配，那么就把该偶数让给当前奇数
// 否则该奇数不能找到匹配
visited := make([]bool, n) //记录第i个偶数在本轮匹配中是否被访问过
matched := make([]int, n) //记录与第i个偶数匹配的奇数
var match func(int) bool //检查该奇数是否能找到合适的匹配, 注意：这是一个闭包函数
match = func(odd int) bool {
for i := 0; i < n; i++ {
if isPrime(odd+evens[i]) && !visited[i] {
visited[i] = true
if matched[i] == 0 || match(matched[i]) {
matched[i] = odd
return true
}
}
}
return false
}
// 为每个奇数寻找匹配
// 每轮的 visited 要清空
for _, odd := range odds {
visited = make([]bool, n)
if match(odd) {
res++
}
}
return res
}
func main() {
var n int
fmt.Scanf("%d", &n)
nums := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scanf("%d", &nums[i])
}
fmt.Println(getMax(nums))
}
GO语言实现 匈牙利算法
package main
import "fmt"
import "io"
import "math"
func main(){
for {
var n int
var num int
var odds []int
var evens []int
c, err := fmt.Scanf("%d\n", &n)
if c==0 || err==io.EOF{
break
}
for i:=0; i<n; i++{
fmt.Scanf("%d", &num)
if num % 2 == 0{
evens = append(evens, num)
}else{
odds = append(odds, num)
}
}
var suited map[int]int = make(map[int]int)
var K int
for i:=0; i<len(odds); i++{
var visited map[int]int = make(map[int]int)
ok := match(odds[i], evens, visited, suited)
if ok {
K++
}
}
fmt.Println(K)
}
}
func match(odd int, evens []int, visited map[int]int, suited map[int]int) bool {
for _, even := range evens{
if isPrime(odd + even) && visited[even] == 0 {
visited[even] = 1
if suited[even] == 0 || match(suited[even], evens, visited, suited) {
suited[even] = odd
return true
}
}
}
return false
}
func isPrime(num int) bool {
n := math.Sqrt(float64(num))
n2 := int(n + 0.5)
for i := 2; i <= n2; i++{
if num%i == 0{
return false
}
}
return true
}
扫描二维码，关注牛客网
下载牛客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(); } } }