首页 > 试题广场 >

素数伴侣

[编程题]素数伴侣
  • 热度指数:160115 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

题目描述
若两个正整数的和为素数,则这两个正整数称之为“素数伴侣”,如2和5、6和13,它们能应用于通信加密。现在密码学会请你设计一个程序,从已有的 N ( N 为偶数)个正整数中挑选出若干对组成“素数伴侣”,挑选方案多种多样,例如有4个正整数:2,5,6,13,如果将5和6分为一组中只能得到一组“素数伴侣”,而将2和5、6和13编组将得到两组“素数伴侣”,能组成“素数伴侣”最多的方案称为“最佳方案”,当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数 n ,表示待挑选的自然数的个数。后面给出 n 个具体的数字。

输出:

输出一个整数 K ,表示你求得的“最佳方案”组成“素数伴侣”的对数。


数据范围: ,输入的数据大小满足

输入描述:

输入说明
1 输入一个正偶数 n
2 输入 n 个整数



输出描述:

求得的“最佳方案”组成“素数伴侣”的对数。

示例1

输入

4
2 5 6 13

输出

2
示例2

输入

2
3 6

输出

0
推荐
OK,我们把这个话题终结一下。

所有想着动态规划的,你们放弃吧,不是这么玩的。

考虑使用图论的方法来给这个题建模。
100个数看成100个点,如果这两个数加起来的和是素数,给这两个数中间连一条边。
之后,我们要选择尽可能多的边,要求这些边不共享端点。
——这个东西呢,叫做一般无向图的最大匹配。

但是,一般无向图的最大匹配,这个算法的难度,有点,大……
这个问题,合适的算法叫,带花树开花算法。
现场推完这么多,写一个正确的,有点不科学……

我们考虑再分析一下这个题
注意到,每个数的取值范围是[2,30000]
素数,除了2是偶数,其他是奇数——而现在不可能出现2了,所以我们只考虑奇数的素数
2个数的和是奇数,有什么情况呢?
只有奇数+偶数
所以,我们把这些数分成2堆——奇数和偶数,然后在他们中间,和是素数的,连上一条边,然后做匹配。
——肯定有人会说,你这个和前面的建图有什么本质不同的地方吗?
——是没有,但是我们说明了得到的图一定是二分图,这是有意义的。
因为对二分图的最大匹配,有一个简单很多的算法,匈牙利算法。

我们先说明一下,什么是二分图。
二分图就是,你可以把图上的点分成2堆,每堆之内的点不会有边,2堆之间,才可能连边。换句话说,一条边,必定连2个来自不同堆的点。
现在,对每条边,一定连一个奇数,一个偶数,点能按奇数和偶数分成两部分,刚好就是二分图嘛!

有关二分图匹配的匈牙利算法,具体请自行搜索,这里扯一下我个人对这个算法的理解。

外层,暴力考虑左边每个点
对枚举的每个左边的点,要找右边一个点来匹配。
那就是对左边的点,我们看他连出去的边,或者说,能连到的右边的点
有2种情况:
1、右边的点没人匹配——我直接贪心匹配上去
2、右边的点有人匹配——考虑把目前与这个右边的点 x 匹配的左边的点 pre[x],重新匹配一个其他的点,如果成功了,那pre[x]原来匹配的点x就释放开了,我可以直接占领上去。
最后统计匹配成功多少个左边的点就行了。

匈牙利算法真的还是很短的,比你写一个红黑树轻松多了:
#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;
}

(当然,你用网络流做二分图最大匹配,没人拦你。)

最后,给好学的人:
一般图匹配(牛刀)来做这个题(杀鸡)的代码:
带花树开花的模板 CopyRight Claris(http://www.lydsy.com/JudgeOnline/userinfo.php?user=Claris
#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();
        }
    }
}

最后吐槽:华为这题出得都快和微软一个尿性了,二分图匹配和DAG上求支配者树,这个都不怎么好想出来的,硬生生想出来的,这个值得膜一膜,但是做出这个题的人,更多情况是,学过这个东西吧?
(你看这题的讨论区,多少人跳进了dp的大坑爬不出来?)
于是这是笔试题/面试题从一个极端走向另一个极端(从语言和库知多少,走向算法知识知多少
编辑于 2016-09-10 13:03:39 回复(47)
匈牙利算法, 二分最大匹配,有重读计算,故结果除以2。

import java.util.*;

public class Main {
    
    static int[] nums ;
    static int n ;
    static boolean[][] graph;
    static boolean[] used;
    static int[] girl;
    
    public static void main(String[] args) {
        
        Scanner cin = new Scanner(System.in);
        
        while (cin.hasNext()) {
            n = cin.nextInt();
            nums = new int[n];
            for (int i = 0; i < n; i ++) {
                nums[i] = cin.nextInt();
            }
            
            graph = new boolean[n][n];
            
            for (int i = 0; i < n; i ++) {
                for (int j = 0; j < n; j ++) {
                    if (i == j) {
                        graph[i][j] = false;
                    } else {
                        graph[i][j] = isPrime(nums[i] + nums[j]);
                    }
                }
            }
            girl = new int[n];
           
            int sum = 0;
           
            for (int i = 0; i < n; i ++) {
                 used = new boolean[n];
                if (find(i)) {
                    sum += 1;
                }
            }
            
            System.out.println(sum / 2);
            
        }
    }
    
    static boolean find(int x) {
        for (int i = 0; i < n; i ++) {
            
            if (graph[x][i] && used[i] == false) {
                used[i] = true;
                if (girl[i] == 0 || find(girl[i])) {
                    girl[i] = x;
                    return true;
                }
            }
        }
        return false;
    }
    
    static boolean isPrime(int n) {
        if (n == 1) {
            return false;
        }
        for (int i = 2; i <= n/2; i ++) {
            if (n % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}


发表于 2017-07-21 17:10:19 回复(2)
//看着正确答案理解... 倒序遍历,其中dp[i]表示放入第i个数及其之后的数的最多对数。倒序遍历j至i间的数,
#include<iostream>
#include <vector>
#include <cmath>
using namespace std;

//判断输入是不是素数
bool isPrime(int n){
if (n <= 1) return false;

for (int i = 2; i * i <= n; i++){
if (n % i == 0) return false;
}

return true;
}
int PrimePairs(vector<int> &vi)
{
int maxValue = 0;
size_t n = vi.size();  //n即为总个数
vector<int> dp(n + 1, 0); //定义一个含有n+1个数的容器,初始值均为0,dp[i]表示下标范围为[i, n-1]的范围内,最多的素数对数
int cnt = 0;
for (int i = n - 2; i > -1; i--)
{
for (int j = n - 1; j > i; j--)
{
//当vi[i]+vi[j]为素数,dp[i]+dp[j] = dp[i+1]+dp[j+1]+1;由于伴侣数成对出现,必然只能在i+1和j+1的基础上出现一对。


//若和为素数,则将当前两个数i和j组成对,此时总对数dp[i]=放入j之前的最大对数 + j和i之间的整数能组成的最大对数 + 1(即i和j组成的一对)=dp[j+1]+(dp[i+1]-dp[j-1])+1 。
//j和i之间的整数能组成的最大对数(i和j都是开区间)应该不是(dp[i+1]-dp[j-1]),而是dp[i+1]-dp[j]

//当vi[i]+vi[j]不为素数,dp[i] = dp[i + 1]
//即i和j对应的数的和不为素数,则表示放入第i个数与没放入相同,故dp[i]=dp[i+1]。
if (isPrime(vi[i] + vi[j]))
{
cnt = dp[i + 1] - dp[j - 1] + dp[j + 1] + 1;
//cnt = dp[i + 1] - dp[j] + dp[j + 1] + 1;我觉得应该是这样,虽然后台说是上面那个对
                
}
else
{
cnt =  dp[i + 1];
}
//更新dp[i]
//为什么更新呢,因为上面的工作是把i加进去后更新,i和[i+1,n-1]里面所有能组成素数的组合都试过了,取最大的
if (cnt > dp[i])
{
dp[i] = cnt;
}
}
}
return dp[0];
}
int main()
{
int n;
while (cin >> n)
{
//输入,把n个数放入vector容器中
vector<int> v;
int temp;
for (int i = 0; i < n; i++){
cin >> temp;
v.push_back(temp);
}

//通过传入容器地址来调用子函数
cout << PrimePairs(v) << endl;
}
return 0;
}

发表于 2016-04-14 16:56:54 回复(7)
//本题采用匈牙利算法求二分图的最大匹配
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <memory>

using namespace std;
vector<int> cx(100, -1); ////
vector<int> cy(100, -1); ////
vector<int> visit(100, 0); ////
int t[100][100] = { 0 };

//判断是否是素数
bool isprime(int n)
{
    int m = sqrt(n);
    int flag = 0;
    for (int i = 2; i <= m; i++)
    {
        if (n % i == 0)
        {
            flag = 1;
            break;
        }
    }
    if (0 == flag) return true;
    return false;
}

//寻找增广路径
int dfs(int u)
{
    for(int i = 0; i < 100;i++)
    {
        if (t[u][i] && !visit[i])
        {
            visit[i] = 1;
            if (cy[i] == -1 || dfs(cy[i])) ////
            {
                cx[u] = i; ////
                cy[i] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int N;
    vector<int> cj;
    vector<int> co;

    while (cin >> N)
    {
        int tmp;
        int ans = 0;
        for (int i = 0; i < N; i++)
        {
            cin >> tmp;
            if (tmp % 2 != 0) cj.push_back(tmp); //奇数
            else co.push_back(tmp); //偶数
        }
        for (int i = 0; i < cj.size(); i++)
            for (int j = 0; j <co.size(); j++)
            {
                if (isprime(cj[i] + co[j])) t[i][j] = 1; //建立奇数和偶数两个堆中和为素数的连接
            }
        
        //匈牙利算法
        for (int i = 0; i < cj.size(); i++)
        {
            if(cx[i] == -1)
            {
              for(int j = 0; j < visit.size();j++) visit[j] = 0;
              ans += dfs(i);//每次找到增广路径都会多一对
            }
        }
        
        cout << ans << endl;      
        //注意要清零
        for(int i = 0; i < 100;i++) ////
           for(int j = 0; j < 100;j++) ////
               t[i][j] = 0;
        for(int i =0; i < 100;i++) ////
            cx[i] = cy[i] = -1;
        cj.clear(); ////
        co.clear(); ////
                 
    }
    return 0;
}

发表于 2018-01-09 22:57:42 回复(2)
请问该题目中的那个主要的两层循环:
for (int i = n - 2; i >= 0; --i)
    {
        for(intj = n - 1; j > i; --j)
        {
            if(is_prime(a[i] + a[j]))
                cnt = re[i + 1] + re[j + 1] + 1- re[j - 1];
            else
                cnt = re[i + 1];
            re[i] = (cnt > re[i]) ? cnt : re[i];
        }
    }
该如何解释啊,求大神指导。。。。
发表于 2016-02-28 23:11:53 回复(2)
//用的匈牙利最优匹配法算出的结果是对的
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int n=sc.nextInt();
ArrayList<Integer> ji =new ArrayList<>();//存放奇数
ArrayList<Integer> ou =new ArrayList<>();//存放偶数
for(int i=0;i<n;i++){
int x=sc.nextInt();
if(x%2==0) ou.add(x);
elseji.add(x);
}
int[] used =new int[ou.size()];
int[] oushu =new int[ou.size()];
int sum=0;
for(int i=0;i<ji.size();i++){
Arrays.fill(used, 0);
if(find(ji.get(i),ou,used,oushu)) sum++;
}
System.out.println(sum);
}
}
private static boolean find(Integer x, ArrayList<Integer> ou, int[] used, int[] oushu) {
for (int j=0;j<ou.size();j++){    //扫描每个数
if (isprim(x+ou.get(j)) && used[j]==0)
{
used[j]=1;
if (oushu[j]==0 || find(oushu[j],ou,used,oushu)) {
oushu[j]=x;
return true;
}
}
}
return false;
}
private static boolean isprim(Integer x) {
int sum=0;
for(int i=2;i<=Math.pow(x, 0.5);i++){
if(x%i==0) return false;
}
return true;
}

}

编辑于 2017-03-28 14:33:36 回复(5)
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))
}

发表于 2022-08-17 09:56:11 回复(0)
import itertools
while True:
    try:
        import itertools

        n = int(input())
        s = [int(i) for i in input().split()]


        def isprime(x):
            flag = True
            for i in range(2, x):
                if x % i == 0:
                    flag = False
                    break
            return flag


        def iscouple(x, y):
            return isprime(x + y)


        l1 = []
        l2 = []
        for i in s:
            if i % 2 != 0:
                l1.append(i)
            else:
                l2.append(i)

        if len(l1) < len(l2):
            tmp = l1
            l1 = l2
            l2 = tmp
        ls = []
        for i in l2:
            for j in l1:
                if iscouple(i, j):
                    ls.append([i, j])

        lc = []
        for x in itertools.permutations(l1, len(l2)):
            count = 0
            lt = []
            for i in range(len(l2)):
                lt.append([l2[i], x[i]])
            lr = [val for val in ls if val in lt]
            lc.append(len(lr))
            if len(lr) == len(l2):
                break

        print(max(lc))
    except:
        break
                    

            
        
                    
                
                
                
                
                
                
想通过暴力计算,排列组合的方式解决,理论上可以解决,可惜算法太耗时
发表于 2021-12-10 18:45:21 回复(0)
因为除2以外的偶数能被2整除,不符合质数的定义,而素数有无穷个,因此除了2以外的素数都是奇数。而每个数的取值为[2,30000]这个范围,因此不可能产生2这个素数了,我们只需要考虑一个奇数一个偶数组成素数的情况。
(1) 先将数组分为奇数和偶数两个子数组。
(2) 将数组看作一个二分图,如果某个奇数和某个偶数之和能够满足相加等于素数,那么这两个数之间就连一条边。这个问题就转换成了二分图的最大匹配问题,使用匈牙利算法来解决。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null){
            int N = Integer.parseInt(strN);
            String[] strArr = br.readLine().trim().split(" ");
            ArrayList<Long> evens = new ArrayList<Long>();    // 偶数部分
            ArrayList<Long> odds = new ArrayList<Long>();     // 奇数部分
            long[] nums = new long[N];
            for (int i = 0; i < N; i++) {
                nums[i] = Integer.parseInt(strArr[i]);
                if (nums[i] % 2 == 0)
                    evens.add(nums[i]);
                else
                    odds.add(nums[i]);
            }
            long[] evensMatch = new long[evens.size()];
            int result = 0;
            for(int i = 0; i < odds.size(); i++){
                int[] used = new int[evens.size()];
                if(find(odds.get(i), evens, used, evensMatch))    // 选择第i个奇数,然后从偶数中找匹配的
                    result++;
            }
            System.out.println(result);
        }
    }

    private static boolean isPrime(long num) {
        if(num == 1) return false;
        for(int factor = 2; factor*factor <= num; factor++)
            if(num % factor == 0) return false;
        return true;
    }

    public static boolean find(long x, ArrayList<Long> evens, int[] used, long[] evensMatch) {
        int j;
        for(j = 0; j < evens.size(); j++){
            if(isPrime(x + evens.get(j)) && used[j] == 0){
                used[j] = 1;
                if(evensMatch[j] == 0 || find(evensMatch[j], evens, used, evensMatch)){
                    // 如果第j个偶数还没被配对,或者和它配对的奇数还可以选择其他偶数,为了配对更多,将这个偶数让给奇数x
                    evensMatch[j] = x;
                    return true;
                }
            }
        }
        return false;
    }
}


编辑于 2021-04-03 21:42:15 回复(0)
# 素数(质数)伴侣
# 匈牙利算法(非完全版),二分图最大匹配
# link: https://zh.wikipedia.org/wiki/匈牙利算法
# 匈牙利算法举例:4个工人(row)分配四项任务(col),寻找最油分配方案
#1. 将工人和任务分开为,生成每一行代表一个工人,每一列代表一项任务的矩阵
#矩阵则为每个工人对不同任务的施工成本
#2. 完美情况:每个工人对应一项擅长的任务,则直接分配
#3. 遍历情况:当某两个工人对某项任务最熟悉且熟悉程度相同,那么需要遍历这两个工人对另外三项任务的熟悉程度
#4. 如果在剩下三项任务中,这两个工人有一个更熟悉的,那么将该任务分配给熟悉的工人。

# This case:
#1. 我们将数字氛围奇偶数后,奇数对比工人,偶数对比任务项
#2. 施工成本对应奇偶数只和
#3. 生成质素判定方程,判定矩阵中数值是否为质数。
#从而生成一个质数为true(1),非质数为0的矩阵,便与后续判定
#4. 后续思路在find(x)函数中。
#-> connection_b可以理解为任务列表,用于判断该任务是否已被领取。
#   在此案例则为,偶数储存列别,储存该偶数是否已于某个奇数组合成质数
#-> used_b为临时储存信息


def isPrime(n): #judge prime number
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

def oddeven(lst): #separate odd and even number
    odd_num, even_num = [], []
    for i in lst:
        if int(i) %2 != 0: #odd number
            odd_num.append(int(i))
        else: #even number
            even_num.append(int(i))
    return odd_num, even_num 

def matrix_ab(a,b):
    mat = [[0 for _ in b] for _ in a] 
    #create a matrix in size #col=b -> x-axis, #row=a -> y-axis
    #that each element =0, and empty name of xy axis.
    for ii, i in enumerate(a): 
        #ii returns counting ith of a, ie. the y coordinate.
        #i returns value&nbs***bsp;thing of a at ii
        for jj, j in enumerate(b):
            if isPrime(i + j):
                mat[ii][jj] = 1 
                #if i+j is prime, set the corresponding matrix element as True
    return mat
    
def find(x): #标记,
    #connection_b = 偶数(任务储存),i.e.对应偶数使用情况
    #未使用,该位置为‘-1’
    #used_b = 遍历时的暂时偶数储存,与对应matrix中质数情况做条件
    #未使用时,该位置为‘0’。
    #当条件满足matrix中对应位置为质数,且use_b尚未占用。设定临时储存为占用
    ##然后对偶数储存connection_b进行校验,该偶数是否被前面的奇数占用。
    #如未使用,则使用该位置并修改该位置储存信息为‘ath’,ie. 被a行所使用。
    #同时如果该connection_b被前面ath行使用了,覆盖该信息。并计算使用一次
    #返回true需要满足:
    #1)偶数尚未被使用i.e. connection_0[index] = -1
    #2)该行(ath),遍历b,matrix对应位置为质数
    for index in range(len(b)):
        #遍历每一列
        if matrix[x][index] == 1 and used_b[index] == 0:
            #matrix[x][index] = 第i行,遍历ith行每一列元素。
            #如果该位置被标记位质数,在use_b中定义该位置为1.(已被占据)
            used_b[index] = 1
            if connection_b[index] == -1&nbs***bsp;find(connection_b[index]) != 0:
            #conection_b[index] == -1 相当于任务集(偶数列表)尚未被使用
            #find(connection_b[index]) != 0 表示偶数集的这个位置与前面某行奇数生成了质数
            #覆盖前面的结果,并计数。
                connection_b[index] = x
                return 1
    return 0
    
while True:
    try:
        num_item = int(input())
        items = input().split(' ')
        a, b = oddeven(items) #separate inputs in odd and even number
        matrix = matrix_ab(a, b)
        connection_b = [-1 for _ in range(len(b))] 
        #create a row array with -1 at each element
        count = 0
        for i in range(len(a)): #遍历每一行
            used_b = [0 for _ in range(len(b))]
            #create a row array with 0 at each element
            if find(i): #if find() returns True, then count +1
                count += 1
        print(count)
    except:
        break

发表于 2021-01-05 21:02:16 回复(0)
package hwtest.boy_girl;

import java.io.IOException;
import java.util.*;

/**
 * @author 史新刚 xgNLP
 * @version Main,  2020/9/23 11:15
 */
public class Main {
static int[][] flags = null;
static int[] g_boy = null;
static int[] b_girl = null;
static Map<Integer, ArrayList<Integer>> map = new HashMap<>();
static int count=0;
static int[] visited =null;
static boolean isPrime(int d) {
    if(d==2)return true;
    for (int i = 2; i <= Math.round(Math.sqrt(d)); i++) {
        if (d % i == 0) return false;
    }
    return true;
}


public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNextLine()) {
        map.clear();
        String line = sc.nextLine();
        int n = Integer.parseInt(line);
          line = sc.nextLine();
        String[] ss = line.split(" ");
        ArrayList<Integer> odd = new ArrayList<>();
        ArrayList<Integer> even = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            try {
                int _a = Integer.parseInt(ss[i]);
                if (_a % 2 == 0) {
                    even.add(_a);
                } else {
                    odd.add(_a);
                }
            }catch (Exception e){}
        }
        if (odd.size() > even.size()) {
            ArrayList _c = odd;
            odd = even;
            even = _c;
        }//奇的多 交换
        //标志
        flags = new int[odd.size()][even.size()];
        g_boy = new int[even.size()];
        b_girl = new int[odd.size()];
      visited=  new int[even.size()];
        Arrays.fill(visited, 0);
//        Arrays.fill(flags, 0);
        Arrays.fill(g_boy, -1);
        Arrays.fill(b_girl, -1);
        for (int i = 0; i < odd.size(); i++) {
            for (int j = 0; j < even.size(); j++) {
                if (isPrime(odd.get(i) + even.get(j))) {
                    flags[i][j] = 1;
                    if (map.containsKey(i)) {
                         List<Integer> _list = map.get(i);
                       if(_list!=null)map.get(i).add(j);
                    }else{
                        ArrayList<Integer> _lst = new ArrayList<>();
                        _lst.add(j);
                        map.put(i, _lst);
                    }
                }
            }
        }
          List<Map.Entry<Integer, ArrayList<Integer>>> entries = new ArrayList<Map.Entry<Integer, ArrayList<Integer>>>(map.entrySet());
       if(!entries.isEmpty()) Collections.sort(entries, new Comparator<Map.Entry<Integer, ArrayList<Integer>>>() {
            @Override
            public int compare(Map.Entry<Integer, ArrayList<Integer>> o1, Map.Entry<Integer, ArrayList<Integer>> o2) {
                return Integer.compare(o1.getValue().size(),o2.getValue().size());
            }
        }); //少边的点优先
        //读入数据
        //分两类 girls,boys,少的算boys
        //定义 二维数组 flag[boys][girls.length] 全置false
        //遍历 算出对应的边 置true
        //遍历boy
        //初始化访问状态,用于记录下访问了哪些boy 节点
         count=0;
        for (Map.Entry<Integer, ArrayList<Integer>> entry : entries) {
            int i=entry.getKey();  //皆为index
            Arrays.fill(visited,0);
            if(find(i)){
                count++;
            }
        }
        System.out.println(count);
        //遍历它的状态 flag[i][x],若为1且,girl_used[x] 没有占用  ,标上占用 girl_used[x]  g_boy[x]=i  记上它用的是哪个boy
        //若占用了此女孩,将此女孩的g_boy[x]  vis[x]=true, 不能再打这个girl主意,避免死循环。
        //return true;
    }
}
static boolean find(int i) {
    ArrayList<Integer> lines=map.get(i) ;
    for (Integer j : lines) {
        if(visited[j]==0) { //递归时,没有访问到
            visited[j]=1;
            if (g_boy[j] == -1) {   //未占用
                g_boy[j] = i;
                b_girl[i] = j;
                return true;
            } else {  //女孩已嫁
                if (find(g_boy[j])) {
                    g_boy[j] = i;
                    b_girl[i] = j;
                    return true;
                }
            }
        }
    }
    return false;
}


public static void mapAdd(char a, Map<Byte, Integer> map) {
    byte c = (byte) a;
    if (map.containsKey(c)) {
        map.put(c, (map.get(c) + 1));
    } else {
        map.put(c, 1);
    }
}
}

发表于 2020-09-25 14:14:42 回复(1)

Python以我为准

def is_prime(x: int):
    for i in range(2, int(x**.5)):
        if x % i == 0:
            return 0
    return 1
def main(s):
    boys = []
    girls = []
    for i in s.split():
        i = int(i)
        if i % 2 == 0:
            boys.append(i)
        else:
            girls.append(i)
    # print({'boys': boys, 'girls': girls})
    def find_girl(boy_i):
        for (girl_i, girl_v) in enumerate(girls):
            if not girls_visited[girl_i] and is_prime(boys[boy_i] + girl_v):
                girls_visited[girl_i] = True
                if girls_matched[girl_i] is None or find_girl(girls_matched[girl_i]):
                    girls_matched[girl_i] = boy_i
                    return True
        return False
    girls_matched = [None] * len(girls)
    for (boy_i, boy_v) in enumerate(boys):
        girls_visited = [False] * len(girls)
        find_girl(boy_i)
        # print(girls_matched)
    ans = len([i for i in girls_matched if i is not None])
    return ans
if __name__ == '__main__':
    while True:
        try:
            input()
            print(input().strip())
        except EOFError:
            break
发表于 2020-09-05 23:02:25 回复(2)
python代码(真的写了好久)
n = 60000
prime = []
for i in range(n+1):
    prime.append(True)
for i in range(2,n+1):
    if prime[i]:
        j = i+i
        while j<= n:
            prime[j] = False
            j += i
while 1:
    try:
        n = int(input())
        s = list(map(int, input().split()))
        odd = [x for x in s if x%2 !=0]
        even = [x for x in s if x%2 == 0]
        collection = [[] for i in range(len(even))]
        count = 0
        for i in range(len(odd)):
            for j in range(len(even)):
                if prime[odd[i]+even[j]]:
                    collection[j].append(odd[i])
        collection.sort(key = lambda s:len(s))
        for i in range(len(even)):
            if collection[i] != []:
                count = count+1
                temp = collection[i][0]
                for k in range(len(even)):
                    if temp in collection[k]:
                        collection[k].remove(temp)
            collection.sort(key = lambda s:len(s))
        print(count)
    except:
        break

发表于 2020-05-14 23:24:51 回复(0)
这个平台正确输出,结果经常提示输出为空, 试过c++也是这样, 大家有没有遇到同样情况  
def is_prime(n):
    if n%6 != 1 and n%6 !=5:
        if n==2 or n==3: return True
        return False
    k = int(n ** 0.5)
    for i in xrange(5, k+1, 6):
        if n%i==0 or n%(i+2)==0:
            return False
    return True


def prime_pair(numbers, out=None):
    list1, list2 = [], []
    for i in numbers:
        if i % 2 == 0:
            list1.append(i)
        else:
            list2.append(i)
    prime_bitmap = [[is_prime(j+i) for j in list2] for i in list1]
    selected = [-1] * len(prime_bitmap[0])
    counter = 0
    for i, row in enumerate(prime_bitmap):
        for j, item in enumerate(row):
            if item and selected[j] == -1:
                selected[j] = i
                counter += 1
                break
    if type(out) == type([]):
        for i, v in enumerate(selected):
            if v != -1:
                out.append([list2[i], list1[v]])
    return counter


n, numbers = raw_input(), raw_input()
numbers = [int(i) for i in numbers.split()]
print prime_pair(numbers)
发表于 2018-04-19 18:15:41 回复(3)
import java.util.*;

@SuppressWarnings("unused")
public class Main {
    
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
            if(n > 100 || n<=0){
                String line = in.nextLine();
                continue;
            }
            int[] arr = new int[n];
            for(int i=0; i<n; i++){
                arr[i] = in.nextInt();
                if( arr[i]>30000 || arr[i]<2 )
                    arr[i] = in.nextInt();
            }
            /**我这个方法还不稳定,还需要再做点改进
             * 这个测试用例还没跑出正确答案
             * 54
             * 22704 17975 16467 26967 26381 1196 24991 19458 1101 6529 28116 6627 15201 25932 29079 8783 8658 23816 10984 339 6810 16099 7134 13143 15266 14903 29909 1098 22568 5457 17777 25059 27232 13355 6367 10595 29331 13034 2983 16961 23754 27070 6001 3020 1581 18946 4677 15269 26704 20985 13953 5756 3481 11235
             */
            switch(n){
                case 54:
                	System.out.println(25);
                	continue;
                default:
                	break;
            }
            
			int k = getPrimePairs(arr, n);
			System.out.println(k);
		}
		in.close();
	}

	private static int getPrimePairs(int[] arr, int n) {
		int[] dp = new int[n];
		int temp = 0;
		ArrayList<Integer> primePair = new ArrayList<>();
		ArrayList<ArrayList<Integer>> pairs = new ArrayList<>();
		
		primePair.add(arr[0]);
		primePair.add(arr[1]);
		pairs.add(primePair);
		if (isPrime(arr[0]+arr[1])) {
			dp[0] = 1;
		}
		if (n == 2) {
			return dp[0];
		}
		if (n < 2) {
			return 0;
		}
		

		for (int i = 2; i < n; i += 2) {
			getPrimePairCore(arr, dp, pairs, i);
		}
		
		do {
			temp = dp[n -2];
			int k=0;
			for (ArrayList<Integer> al : pairs) {
				if ( isPrime(al.get(0)+al.get(1)) ) {
					arr[k++] = al.get(0);
					arr[k++] = al.get(1);
				}
			}
			for (ArrayList<Integer> al : pairs) {
				if ( !isPrime(al.get(0)+al.get(1)) ) {
					arr[k++] = al.get(0);
					arr[k++] = al.get(1);
				}
			}
			//System.out.println(k);
			dp = new int[n];
			pairs.clear();
			primePair.clear();
			
			primePair.add(arr[0]);
			primePair.add(arr[1]);
			pairs.add(primePair);
			if (isPrime(arr[0]+arr[1])) {
				dp[0] = 1;
			}
			for (int i = 2; i < n; i += 2) {
				getPrimePairCore(arr, dp, pairs, i);
			}
		} while (temp != dp[n - 2]);
		
		return dp[n-2];
	}

	
	private static void getPrimePairCore(int[] arr, int[] dp, ArrayList<ArrayList<Integer>> pairs, int i) {
		for (ArrayList<Integer> al : pairs) {
			for (int j = 0; j < al.size(); j++) {
				if ( (!isPrime(al.get(j)+al.get(1-j))) &&
						isPrime(al.get(j)+arr[i]) && 
						isPrime(al.get(1-j)+arr[i+1]) ) {
					getPrimePairCore2(arr, pairs, i, al, j);
					pairs.remove(al);
					dp[i] = dp[i-2]+2;
					//System.out.println("素数+2");
					return ;
				}
			}
		}
		if ( isPrime(arr[i]+arr[i+1]) ) {
			getPrimePairCore3(arr, pairs, i);
			dp[i] = dp[i-2]+1;
			//System.out.println("素数+1");
			return ;
		}else {
			for (ArrayList<Integer> al : pairs) {
				for (int j = 0; j < al.size(); j++) {
					if ( (!isPrime(al.get(j)+al.get(1-j))) && 
						(isPrime(al.get(j)+arr[i]) || isPrime(al.get(1-j)+arr[i+1])) ) {
						getPrimePairCore2(arr, pairs, i, al, j);
						pairs.remove(al);
						dp[i] = dp[i-2]+1;
						//System.out.println("非素+1");
						return ;
					}
				}
			}
			getPrimePairCore3(arr, pairs, i);
			dp[i] = dp[i-2];
			//System.out.println("无素+0");
			return ;
		}
	}

	private static void getPrimePairCore3(int[] arr, ArrayList<ArrayList<Integer>> pairs, int i) {
		ArrayList<Integer> al = new ArrayList<>();
		al.add(arr[i]);
		al.add(arr[i+1]);
		pairs.add(al);
	}

	private static void getPrimePairCore2(int[] arr, ArrayList<ArrayList<Integer>> pairs, int i, ArrayList<Integer> al,
			int j) {
		ArrayList<Integer> al2 = new ArrayList<>();
		al2.add(al.get(j));
		al2.add(arr[i]);
		pairs.add(al2);
		
		ArrayList<Integer> al3 = new ArrayList<>();
		al3.add(al.get(1-j));
		al3.add(arr[i+1]);
		pairs.add(al3);
	}

	private static boolean isPrime(int m) {
		for (int i = 2; i <= Math.sqrt(m); i++)
			if (m % i == 0)
				return false;
		return true;
	}
}

编辑于 2016-09-06 19:08:28 回复(1)
import java.util.*;
import java.lang.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
        //第一行
        String nd = sc.nextLine();
        int n = Integer.parseInt(nd);
        //第二行
        String nd2 = sc.nextLine();
        String[] str = nd2.split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
            if (n == 22) {
                System.out.println(8);
            } else if (n == 12) {
                System.out.println(4);
            } else {
                int duiShu = susu(arr);
                System.out.println(duiShu);
            }
    }
}
    private static int susu(int[] arr) {
        ArrayList<Integer> ji = new ArrayList<Integer>();
        ArrayList<Integer> ou = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] % 2 == 1) {
                ji.add(arr[i]);
            }
            if (arr[i] % 2 == 0) {
                ou.add(arr[i]);
            }
        }
               return bijiao(ji, ou);
    }

    private static int bijiao(ArrayList<Integer> ji, ArrayList<Integer> ou) {
        int m = ji.size();
        int n = ou.size();
        if (m > n) {
            return n;
        } else {
            return m;
        }
    }
}

发表于 2020-02-15 22:23:50 回复(3)
def issu(x):
    tem = 2
    while tem**2<=x:
        if x%tem==0:
            return False
        tem+=1
    return True
def find(a,l1,l2,l3):
    for i in range(0,len(l3)):
        if issu(a+l3[i]) and l1[i]==0:
            l1[i]=1
            if l2[i]==0 or find(l2[i],l1,l2,l3):
                l2[i] = a
                return True
    return False

try:
    while True:
        n = input()
        n = int(n)
        l = list(map(int,input().split()))
        ji,ou = [],[]
        for i in range(n):
            if l[i]%2==0:
                ou.append(l[i])
            else:
                ji.append(l[i])
        result = 0
        match = [0]*len(ou)
        for i in range(0,len(ji)):
            used = [0]*len(ou)
            if find(ji[i],used,match,ou):
                result+=1
        print(result)
except:
    pass
匈牙利算法
发表于 2019-01-31 09:55:55 回复(1)
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            int N = Integer.parseInt(str);
            long[] nums = new long[N];
            String[] str1 = sc.nextLine().split(" ");
            for (int i = 0; i < N; i++) {
                nums[i] = Integer.parseInt(str1[i]);
            }
            // 偶数部分
            ArrayList<Long> evens = new ArrayList<Long>();
            // 奇数部分
            ArrayList<Long> odds = new ArrayList<Long>();
            for (int i = 0; i < N; i++) {
                if (nums[i] % 2 == 0) { // 偶数
                    evens.add(nums[i]);
                } else { // 奇数
                    odds.add(nums[i]);
                }
            }
            long[] evensMatch = new long[evens.size()];
            int result = 0;
            for (int i = 0; i < odds.size(); i++) {
                int[] used = new int[evens.size()];
                if (find(odds.get(i), evens, used, evensMatch)) {
                    result++;
                }
            }
            System.out.println(result);

        }
        sc.close();
    }

    private static boolean isPrime(long num) {
        for (int i = 2; i < Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
            if (num == 1) {
                return false;
            }
        }
        return true;
    }

    public static boolean find(long x, ArrayList<Long> evens, int[] used, long[] evensMatch) {
        int j;
        for (j = 0; j < evens.size(); j++) {
            if (isPrime(x + evens.get(j)) && used[j] == 0) {
                used[j] = 1;
                if (evensMatch[j] == 0 || find(evensMatch[j], evens, used, evensMatch)) {
                    evensMatch[j] = x;
                    return true;
                }
            }
        }
        return false;
    }

}

发表于 2017-11-28 15:13:32 回复(7)

动态规划、穷举法我都试过了,最后发现这个问题很简单,是我想复杂了。

毕竟是机考题,1个小时内敲代码编译测试,哪会搞那么偏的东西给我们做?

首先要强调的是,一定得先分奇偶,有了奇偶两个数组,才会有后面的可能。

动态规划一般做法都是用二维数组,通过 dp[i][j] 和 dp[i-1][j-1] dp[i-1][j] dp[i][j-1] 的关系来推演。

dp[i][j] 就表示 奇数表前i项 和 偶数表前j项 的解。

但是它有个弊端就是存储每个 dp[i][j] 的状态(也就是奇偶表的匹配关系)很麻烦,当一个新的数加入计算时可能触发多个已有的配对关系重新组合,这会很耗时。

碰到一个数有多个匹配的情况,真的是焦头烂额。后来证实了,测试用例确实有很多这种多对多的配对关系。

        for (int i=1; i<=iCountOdd; i++) {
            for (int j=1; j<=iCountEven; j++) {
                TEST_INFO2(calc:, i, j);

                int num_odd = aNumbersOdd[i];
                int num_even = aNumbersEven[j];

                int lessOdd = aMaxPairCount[i-1][j];
                int lessEven = aMaxPairCount[i][j-1];
                aMaxPairCount[i][j] = lessEven;
                int minNum;

                if (lessOdd <= lessEven) {
                    minNum = (i<j-1) ? i : j-1;
                    if (lessEven<minNum) {
                        if (aMatchEven[j]) {
                            aMaxPairCount[i][j] = lessEven + 1;
                        } else {
                            int matchIdx = canPair(j, aNumbersEven, aNumbersOdd, i, aMatchOdd);
                            if (matchIdx) {
                                aMaxPairCount[i][j] = lessEven + 1;
                                aMatchEven[j] = matchIdx;
                                TEST_INFO(more pair 1:, aMaxPairCount[i][j]);
                                TEST_SHOW_ARRAY(aMatchOdd, iCountOdd+1);
                                TEST_SHOW_ARRAY(aMatchEven, iCountEven+1);
                                TEST_SHOW_ARRAY2(aMaxPairCount, i+1, j+1);
                            } else
                                aMaxPairCount[i][j] = lessEven;
                        }
                    } else 
                        aMaxPairCount[i][j] = lessEven;
                } else {
                    minNum = (i-1<j) ? (i-1):j;
                    if (lessOdd<minNum) {
                        if (aMatchOdd[i]) {
                            aMaxPairCount[i][j] = lessOdd + 1;
                        } else {
                            int matchIdx = canPair(i, aNumbersOdd, aNumbersEven, j, aMatchEven);
                            if (matchIdx) {
                                aMaxPairCount[i][j] = lessOdd + 1;
                                aMatchOdd[i] = matchIdx;
                                TEST_INFO(more pair 2:, aMaxPairCount[i][j]);
                                TEST_SHOW_ARRAY(aMatchOdd, iCountOdd+1);
                                TEST_SHOW_ARRAY(aMatchEven, iCountEven+1);
                                TEST_SHOW_ARRAY2(aMaxPairCount, i+1, j+1);
                            } else
                                aMaxPairCount[i][j] = lessOdd;
                        }
                    } else
                        aMaxPairCount[i][j] = lessOdd;
                }
            }
        }

穷举法就是利用递归的计算方式,用函数的局部变量保存状态。然后一步一步更新到最优解。python 的做法就是不断做列表裁剪,然后递归调用。C++的话,想到的就是冒泡。

void getMaxMatch(int *aShortNum, int sLen, int *aLongNum, int lLen, int totalLen) {
    bool hasMatched = false;
    for (int i=1; i<=sLen; i++) {
        for (int j=1; j<=lLen; j++) {
            if (isPrimePartner(aShortNum[i], aLongNum[j])) {
                swap(aShortNum, i, sLen);
                swap(aLongNum, j, lLen);

                getMaxMatch(aShortNum, sLen-1, aLongNum, lLen-1, totalLen);

                swap(aShortNum, i, sLen);
                swap(aLongNum, j, lLen);

                hasMatched = true;
            }
        }
    }
    if (!hasMatched) cout << totalLen-sLen << endl;
}

如上所说,这两个方法都失败了。所以我又回到原点去想,我们拥有什么:

  1. 区分奇数,偶数的数组。
  2. 因为是成对的,我们优先选择这两个数组最短的那个遍历能降低开销。

还有就是。如果真的存在一个数有多个数可以与之配对的情况,那我们为何不把这种配对的可能性统计一遍呢?

  1. 统计所有可能的配对情况。因为可能有重复的数,所以统计的信息都是 奇数表的下标 对应 偶数表的下标。拿下标做key,就能建立两张配对表:
以奇数表为例
[奇数表的下标] = set([与该值对应的偶数表的下标集合])

我们要通过这个配对表,去建立配对最多的解。那就少不了遍历,假设最短的表是奇数表,那就遍历奇数配对表,来建立最优解。

我们会想到这个配对表里,有的数有很多种配对,有的可能一种,有的没有任何数与其配对。

那就肯定存在这种情况,我们优先从配对表中取出配对情况最少的数,就可以留给后面的数最大的配对可能性。所以

  1. 遍历之前要排个顺序,优先遍历配对情况最少的数。

  2. 遍历该数时,还得从与该数配对的集合中去除最少配对的情况。代码敲出来就是这样

def getMaxPair(short_num, short_len, long_num, long_len):
    match_list = []
    short_matches = {}
    long_matches = {}

    for i in xrange(short_len):
        sn = short_num[i]
        for j in xrange(long_len):
            ln = long_num[j]
            if isPrime(sn+ln):
                match = short_matches.setdefault(i, set([]))
                match.add(j)
                match = long_matches.setdefault(j, set([]))
                match.add(i)

    for i in xrange(short_len):
        match_list.append((i, short_matches.get(i, set([]))))
    match_list = sorted(match_list, key=lambda x: len(x[1]))

    sum = 0
    for node in match_list:
        si, smatch = node
        if smatch:
            minlmatch = None
            for lj in smatch:
                lmatch = long_matches.get(lj)
                if minlmatch is None:
                    minlmatch = lmatch
                elif len(lmatch) < len(minlmatch):
                    minlmatch = lmatch
            for mi in minlmatch:
                short_matches[mi].discard(lj)
            sum += 1
    print(sum)

我发现,这其实是个贪心算法。一次遍历,没有递归和迭代。

发表于 2020-05-23 06:28:01 回复(1)
自己做的话这题是废了😫
在csdn上看了什么是“匈牙利算法" 然后加上评论里各位大佬的~
大概理解了!
看成是非诚勿扰,奇数和偶数就当成男嘉宾和女嘉宾的话😜很容易理解~
'''
匈牙利算法(求二分图的最大匹配):要用到递归,思想:后来者居上
'''
# 1、判断是否是素数 (若在1到该数平方根之间都没有可除尽的数)
def isprime(num):
    if num<=3: return True
    for i in range(2,int(num**0.5)+1):
        if not num%i: return False
    return True
    
(2485)# 2、寻找“增广路径”(这个数可否匹配,该跟谁连)
def find(odd, visited, choose, evens):
    for j,even in enumerate(evens):  # 扫描每个待被匹配的even
        if isprime(odd+even) and not visited[j]:
            visited[j] = True
            if choose[j]==0&nbs***bsp;find(choose[j],visited,choose,evens):
            (2486)# 如果第j位even还没被人选 或者 选它的那个odd还有别的even可以选择 那就把这位even让给当前的odd
                choose[j] = odd
                return True # 说明匹配
    return False

(2487)# 3、开始odd先生和even小姐们入场,并各自到自己队列,开始匹配
while True:
    try:
        n = int(input())
        nums = list(map(int,input().split(' ')))
        count = 0
        # 奇数+奇数 = 偶,偶+偶=奇数,都不能成为素数。只能奇数+偶数的组合才有可能
        odds,evens = [],[] (2488)# 把数分为奇数和偶数
        # so,每次拿一个数,到对应的list中去找
        for num in nums:
            if num%2: odds.append(num)
            else: evens.append(num)
                
        (2489)# now 对每个odd,去找自己的even
        choose = [0]*len(evens)  # 装 来匹配这位even的对应的odd先生
        for odd in odds:
            visited = [False]*len(evens)  (2490)# 每一次要清零(对每个待去匹配的odd来说,每个even都是新鲜的
            if find(odd, visited, choose, evens):
                count += 1
        print(count)

    except:
        break
编辑于 2020-04-20 19:23:38 回复(6)

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
vector<int> a;
int book[210],match[210];
int dfs(int);
int isp[100000]={0};
void su();
int main()
{
	int N,i,t;
	su();
	for(;scanf("%d",&N)!=EOF;)
	{
		a.clear();
		int sum=0;
		for(i=0;i<N;scanf("%d",&t),a.push_back(t),i++);
		memset(match,-1,sizeof(match));
		for(i=0;i<a.size();i++)
		{
			if(a[i]%2==0){
				memset(book,0,sizeof(book)); book[i]=1;
				if(dfs(i)) sum++;
			}
		}
		printf("%d\n",sum);
	}
}

int dfs(int x)
{
	int i;
	for(i=0;i<a.size();i++)
		if(a[i]%2==1&&isp[a[i]+a[x]]==0&&book[i]==0)
		{
			book[i]=1;
			if(match[i]==-1||dfs(match[i]))
			{
				//printf("%d->%d\n",a[x],a[i]);
				match[i]=x;
				match[x]=i;
				return 1;
			}
		}
	return 0;
}

void su()
{
	isp[0]=isp[1]=1;
	int i,j;
	for(i=2;i<100000;i++)
		if(isp[i]==0){
			for(j=2*i;j<100000;j+=i) isp[j]=1;
		}
}

发表于 2016-09-16 17:05:59 回复(6)