题解 | 素数伴侣

package main

import (
	"bufio"
	"fmt"
	"os"
    "sort"
)

const MAX = 60000 + 1 // a+b 最大 60000

var isPrime [MAX]bool
var primeList []int

// 线性筛法预处理素数
func sieve() {
	for i := 2; i < MAX; i++ {
		isPrime[i] = true
	}
	for i := 2; i < MAX; i++ {
		if isPrime[i] {
			primeList = append(primeList, i)
			for j := i * 2; j < MAX; j += i { // 所有 i 的倍数都不是素数
				isPrime[j] = false
			}
		}
	}
}

/* 
    素数是奇数+偶数
    二分图配对问题
    以个数少的一方为配对基准（左图left）
    优先对left中可匹配right图数较少的元素进行配对
 */

func main() {
	sieve()

	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	// 读 n
	scanner.Scan()
	var n int
	fmt.Sscan(scanner.Text(), &n)

	// 读 n 个数
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		scanner.Scan()
		fmt.Sscan(scanner.Text(), &nums[i])
	}

	// 分离奇偶
    var evens, odds []int
    for _, x := range nums {
        if x%2 == 0 {
            evens = append(evens, x) // 偶数
        } else {
            odds = append(odds, x) //奇数
        }
    }

    // 决定哪边做左部（如果个数相差较大）：选个数少的
    evensLessOdd :=  float64((len(odds) - len(evens)))/float64(len(evens)) > 0.2

    var left, right []int
    var adj [][]int

    if evensLessOdd {
        left, right = evens, odds
    } else {
        left, right = odds, evens
    }

    // 构建邻接表：left[i] 能和哪些 right[j] 配对
    adj = make([][]int, len(left))
    var sum int
    for i, u := range left {
        for j, v := range right {
            sum = u + v
            if sum < MAX && isPrime[sum] {
                adj[i] = append(adj[i], j)
            }
        }
    }

    // （可选，由于一般相差不大，排序未必更高效）在构建 adj 后，按可匹配数升序排序 left
    indices := make([]int, len(left))
    for i := range indices {
        indices[i] = i
    }
    sort.Slice(indices, func(i, j int) bool {
        return len(adj[indices[i]]) < len(adj[indices[j]])
    })

    // 重新排序 adj（和 left，如果需要）
    newAdj := make([][]int, len(left))
    for i, idx := range indices {
        newAdj[i] = adj[idx]
    }
    adj = newAdj

	// 匈牙利算法求最大匹配
	matchRight := make([]int, len(right)) // matchRight[j] = 哪个 left 的索引匹配了 right[j]
	for i := range matchRight {
		matchRight[i] = -1
	}

    var dfs func(u int, visit []bool) bool 
    dfs = func(u int, visited []bool) bool {
        for _,i := range adj[u] {
            if visited[i] {
                continue
            }
            visited[i] = true
            if matchRight[i] == -1 || dfs(matchRight[i], visited){ 
                // 传的是同一个 visited 数组，因为它表示“在当前这一次增广路搜索中，哪些右部节点已经被尝试过”。
                // 不重置，是为了避免在同一次搜索中重复尝试同一个右部节点，防止无限递归和无效搜索。
                matchRight[i]=u
                return true
            }
        }
        return false
    }

    var matching int =0
    for i:=0;i<len(left);i++ {
        visited := make([]bool, len(right))
        if dfs(i, visited){
            matching++
        }
    }

	fmt.Println(matching)
}