题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
输入:
有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。
输出:
输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数。

由于数字范围是2-30000那么相加之和一定大于2,而大于2的素数一定是奇数,奇数又一定是奇数+偶数之和;
把数字分为两组,其和为素数时即表示路径是通的;

import java.util.*;
public class Main{
    public static boolean isPrime(int num){
        for(int i=2;i<=Math.sqrt(num);i++){
            if(num%i==0) return false;
        }
        return true;
    }
    //匈牙利法()
    public static boolean find(int i,boolean[][] prime,int[] evenToOdd,boolean[] used){
        for(int j=0;j<prime[0].length;j++){
            if(prime[i][j]&&!used[j]){
                used[j]=true;
                int pre = evenToOdd[j];
                // 核心思路---在不影响前面数量的基础上,后面能插进去的话,就后面匹配上,前面再找路子
                if(pre==-1||find(pre,prime,evenToOdd,used)){
                    evenToOdd[j]=i;
                    //prime[i][j]=false;
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int num = scanner.nextInt();
            int[] arr = new int[num];
            for(int i=0;i<num;i++){
                arr[i]=scanner.nextInt();
            }
            // 由于数字范围是2-30000那么相加之和一定大于2,而大于2的素数一定是奇数,奇数又一定是奇数+偶数之和
            // 所以把数字分为两组
            ArrayList<Integer> oddList = new ArrayList<Integer>();
            ArrayList<Integer> evenList = new ArrayList<Integer>();
            for(int i=0;i<arr.length;i++){
                if(arr[i]%2==0){
                    evenList.add(arr[i]);
                }else{
                    oddList.add(arr[i]);
                }
            }
            int oddNum = oddList.size();
            int evenNum = evenList.size();
            if(oddNum==0||evenNum==0){
                System.out.println(0);
                continue;
            }
            // 建立邻接矩阵-描绘图的关系
            boolean[][] prime = new boolean[oddNum][evenNum]; 
            for(int i=0;i<oddNum;i++){
                for(int j=0;j<evenNum;j++){
                    prime[i][j]=isPrime(oddList.get(i)+evenList.get(j));
                }
            }

            // 统计连接
            int[] evenToOdd = new int[evenNum];
            for(int i=0;i<evenToOdd.length;i++){
                evenToOdd[i] = -1;
            }
            int count = 0;
            for(int i=0;i<oddNum;i++){
                // 这步最关键,每次都重新建一个数组来标记是否访问了
                boolean[] used = new boolean[evenNum];
                if(find(i,prime,evenToOdd,used)) count++;
            }
            System.out.println(count);
            
        }
    }
}

图片示例

匈牙利1.png

在做的过程中犯了一个错误(误打误撞还通过了80%🤦‍♂️):

匈牙利2.png