匈牙利算法+递归 | HJ28 素数伴侣

# 最优解
import math
def is_prime(num):
    if num <= 3:
        return num > 1
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0:
            return False
    return True

def match(odd):
    for i, even in enumerate(evens):
        if not visited_evens[i] and is_prime(odd+even):
            visited_evens[i] = True
            if pair[i]==0 or match(pair[i]):
                pair[i] = odd
                return True
    return False

while True:
    try:
        n = int(input())
        nums = list(map(int, input().split(' ')))
        evens, odds = [], []
        for num in nums:
            if num % 2 == 0:
                evens.append(num)
            else:
                odds.append(num)
        cnt = 0
        pair = [0]*len(evens)
        for odd in odds:
            visited_evens = [0] * len(evens)
            if match(odd):
                cnt += 1
        print(cnt)
    except:
        break

# 我的代码（超时未通过）
import math
def is_prime(n):
    if n <= 1:
        return False
    elif n <= 3:
        return True
    elif n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(math.sqrt(n))+1, 6):
        if n % i == 0 or n % (i+2) == 0:
            return False
    return True

def func(nums, groups, visited):
    if sum(visited.values()) == len(nums):
        cnt = 0
        for group in groups:
            if is_prime(group[0]+group[1]):
                cnt += 1
        # res.append((cnt, groups))
        res.append(cnt)
        return True
    for i in range(len(nums)-1):
        if not visited[i]:
            visited[i] = True
            for j in range(i+1, len(nums)):
                if not visited[j]:
                    visited[j] = True
                    groups.append((nums[i], nums[j]))
                    func(nums, groups, visited)
                    visited[j] = False
                    groups.pop()
            visited[i] = False


while True:
    try:
        n = int(input())
        s = list(map(int, input().split(' ')))
        res = []
        visited = {i: False for i in range(n)}
        func(s, [], visited)
        print(max(res))
    except:
        break

用时：3.5h