题解 | #素数伴侣#

理解了一下匈牙利算法，好像是这么个事

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }
        List<Integer> aList = new ArrayList<>();
        List<Integer> bList = new ArrayList<>();
        List<Integer> cList = new ArrayList<>();

        for (int num : nums) { //根据奇偶分到两个list
            if (num % 2 == 0) {
                bList.add(num);
            } else {
                aList.add(num);
            }
        }

        if (aList.size() > bList.size()) { //使aList是总数较小的那个
            List<Integer> t = bList;
            bList = aList;
            aList = t;
        }

        n = aList.size();
        int m = bList.size();
        int[] use = new int[m];
        for (int i = 0; i < m; i++) {//标记use[j] = -1为未使用
            use[i] = -1;
        }
        int maxPartner = 0;
        for (int i = 0; i < n; i++) {
            boolean suc = find(aList, bList, i, use, cList);
            if (suc) {
                maxPartner++;
            }
        }
        System.out.println(maxPartner);
    }

    public static boolean find(List<Integer> aList, List<Integer> bList, int i,
                                   int[]use, List<Integer> cList) {
        int a = aList.get(i);
        for (int j = 0; j < bList.size(); j++) { //优先找没用的
            if (use[j] != -1) {
                continue;
            }
            if (isPrime(a + bList.get(j))) {
                use[j] = i;
                cList.add(j);
                return true;
            }
        }
        
        for(Integer j : cList) { //再找之前用过的，递归过程中标记use[j] = -2锁定这个j不能再被换
            if(use[j] == -2) {
                continue;
            }
            if (!isPrime(a + bList.get(j))) {
                continue;
            }
            int oldUse = use[j];
            use[j] = -2;
            if(find(aList, bList, oldUse, use, cList)) {
                use[j] = i;
                return true;
            }
            use[j] = oldUse;
        }
        return false;
    }


    static Map<Integer, Boolean> cache = new HashMap<>();
    public static boolean isPrime(int number) {
        if (cache.containsKey(number)) {
            return cache.get(number);
        }
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}