题解 | 素数伴侣

def is_prime(x):
    if x < 2:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True


def max_matching(n, nums):
    # 按奇偶分组
    odds = []
    evens = []
    for num in nums:
        if num % 2 == 0:
            evens.append(num)
        else:
            odds.append(num)

    # 建图：左边奇数索引 -> 右边偶数索引
    from collections import defaultdict

    graph = defaultdict(list)
    for i, odd in enumerate(odds):
        for j, even in enumerate(evens):   #enumerate() 同时拿到“索引”和“值”
            if is_prime(odd + even):
                graph[i].append(j)   #实现奇数对多偶数的素数组合

    # 匈牙利算法
    match_right = [-1] * len(evens)  # 右边匹配的左顶点索引

    def dfs(u, visited):
        for v in graph[u]:
            if not visited[v]:
                visited[v] = True
                if match_right[v] == -1 or dfs(match_right[v], visited):   #最关键的点，递归回溯，位置被占了，得看看前面的数能不能让个位置
                    match_right[v] = u
                    return True
        return False

    result = 0
    for i in range(len(odds)):
        visited = [False] * len(evens)
        if dfs(i, visited):
            result += 1
    return result


if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    print(max_matching(n, nums))


裂开，一道题给我整半天，快给我整抑郁了，脑子有点不够用了，递归太久没回顾。难崩，这还华为机考还考个得儿...（又是信心被打击的一天）