题解 | 素数伴侣

package main

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

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

var isPrime [MAX]bool

// 线性筛法预处理素数
func sieve() {
    // 从2开始，先初始化为都是素数
    for i:=2;i<MAX;i++{
        isPrime[i] = true
    }
	for i:=2;i<MAX;i++{
        if isPrime[i] {
            for j:= i*i;j<MAX;j+=i{ // 素数的倍数不是素数
                isPrime[j] = false
            }
        }
    }
}

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

    步骤：
    1）素数集求解
    2）读取数据
    3）奇偶分离（二分）
    4）可配对情况 邻接表adj
    5）尝试配对 函数dfs —— 匈牙利算法
    6）开始配对，并输出结果
 */

func main() {
    /* 1）素数集求解 */
	sieve()

    /* 2）读取数据 */
	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])
	}

    /* 3）奇偶分离（二分） */
	// 分离奇偶
    var odds, evens []int
    for i:=0;i<n;i++{
        if nums[i]%2 ==0{
            evens =append(evens, nums[i])
        }else{
            odds = append(odds, nums[i])
        }
    }

    // 决定哪边做左部（如果个数相差较大）：选个数少的
    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
    }

    /* 4）可配对情况 邻接表adj */
    // 构建邻接表：left[i] 能和哪些 right[j] 配对
    adj = make([][]int, len(left)) // 记录left和right中元素的索引，而非数值
    var t int
    for i:= 0;i<len(left);i++{
        for j:=0;j<len(right);j++{
            t = left[i]+right[j]
            if t < MAX && isPrime[t] {
                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

    /* 5）尝试配对 函数dfs */
	// 匈牙利算法求最大匹配
	matchRight := make([]int, len(right)) // matchRight[j] = 哪个 left 的索引匹配了 right[j]
	for i:=0;i<len(matchRight);i++{
        matchRight[i] = -1 // -1 表示未匹配
    }
    var dfs func(u int, visited []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) {
                matchRight[i] = u
                return true
            }
        }
        return false
    }

    /* 6）开始配对，并输出结果 */
    var matching int =0
    for i:=0;i<len(left);i++ {
        visited := make([]bool, len(right))
        if dfs(i, visited){
            matching++
        }
    }

	fmt.Println(matching)
}