題目描述
若兩個(gè)正整數(shù)的和為素?cái)?shù)蓖乘，則這兩個(gè)正整數(shù)稱之為“素?cái)?shù)伴侶”锤悄，如2和5、6和13嘉抒，它們能應(yīng)用于通信加密×憔郏現(xiàn)在密碼學(xué)會(huì)請(qǐng)你設(shè)計(jì)一個(gè)程序，從已有的N（N為偶數(shù)）個(gè)正整數(shù)中挑選出若干對(duì)組成“素?cái)?shù)伴侶”些侍，挑選方案多種多樣隶症，例如有4個(gè)正整數(shù)：2，5岗宣，6蚂会，13，如果將5和6分為一組中只能得到一組“素?cái)?shù)伴侶”耗式，而將2和5胁住、6和13編組將得到兩組“素?cái)?shù)伴侶”，能組成“素?cái)?shù)伴侶”最多的方案稱為“最佳方案”刊咳，當(dāng)然密碼學(xué)會(huì)希望你尋找出“最佳方案”彪见。
輸入:
有一個(gè)正偶數(shù)N（N≤100），表示待挑選的自然數(shù)的個(gè)數(shù)娱挨。后面給出具體的數(shù)字余指，范圍為[2,30000]。
輸出:
輸出一個(gè)整數(shù)K跷坝，表示你求得的“最佳方案”組成“素?cái)?shù)伴侶”的對(duì)數(shù)酵镜。

由于數(shù)字范圍是2-30000那么相加之和一定大于2,而大于2的素?cái)?shù)一定是奇數(shù),奇數(shù)又一定是奇數(shù)+偶數(shù)之和;
把數(shù)字分為兩組,其和為素?cái)?shù)時(shí)即表示路徑是通的;

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];
                // 核心思路---在不影響前面數(shù)量的基礎(chǔ)上,后面能插進(jìn)去的話,就后面匹配上,前面再找路子
                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();
            }
            // 由于數(shù)字范圍是2-30000那么相加之和一定大于2,而大于2的素?cái)?shù)一定是奇數(shù),奇數(shù)又一定是奇數(shù)+偶數(shù)之和
            // 所以把數(shù)字分為兩組
            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;
            }
            // 建立鄰接矩陣-描繪圖的關(guān)系
            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));
                }
            }

            // 統(tǒng)計(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++){
                // 這步最關(guān)鍵,每次都重新建一個(gè)數(shù)組來(lái)標(biāo)記是否訪問(wèn)了
                boolean[] used = new boolean[evenNum];
                if(find(i,prime,evenToOdd,used)) count++;
            }
            System.out.println(count);
            
        }
    }
}

圖片示例

匈牙利1.png

在做的過(guò)程中犯了一個(gè)錯(cuò)誤(誤打誤撞還通過(guò)了80%???♂?):

匈牙利2.png