2023-03-25：若两个正整数的和为素数，则这两个正整数称之为“素数伴侣“。 给定N(偶数)个正整数中挑选出

2023-03-25：若两个正整数的和为素数，则这两个正整数称之为”素数伴侣”。
给定N(偶数)个正整数中挑选出若干对，组成”素数伴侣”，
例如有4个正整数：2，5，6，13，
如果将5和6分为一组的话，只能得到一组”素数伴侣”，
如果将2和5、6和13编组，将得到两组”素数伴侣”，
这是得到”素数伴侣”最多的划分方案。
输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
输出:
输出一个整数 K ，表示最多能找出几对”素数伴侣”。
数据范围： 1 <= n <= 100, 2 <= val <= 30000。
来自华为。

答案2023-03-05：

用二分图最大匹配来解决。具体步骤如下：

将所有数字看作二分图的左右两部分节点，如果两个节点的和是一个素数，则在它们之间连接一条边。

使用 KM 算法求解二分图的最大匹配。最大匹配的结果就是最多能找到多少对“素数伴侣”。

这里需要注意的是，KM算法的时间复杂度为 O(n^3)，但本题数据范围比较小，因此可以通过。

rust代码如下：

// 构造邻接矩阵
fn matrix(arr: &[i32], n: usize) -> Vec<Vec<i32>> {
    // 判断是否是素数的函数
    let is_prime = |num| (2..(num as f64).sqrt() as i32 + 1).all(|i| num % i != 0);
    let mut ans = vec![vec![0; n]; n];
    for i in 0..n {
        for j in 0..n {
            ans[i][j] = if is_prime(arr[i] + arr[j]) { 1 } else { 0 };
        }
    }
    ans
}

// KM算法实现求解最大匹配
fn km(graph: &[Vec<i32>]) -> i32 {
    let n = graph.len();
    let invalid = i32::MAX;
    let mut match_ = vec![-1; n]; // 记录匹配情况的数组，初始值为-1表示没有匹配
    let mut lx = vec![-invalid; n]; // 左部点的标号
    let mut ly = vec![0; n]; // 右部点的标号
    let mut x = vec![false; n]; // 记录左部点是否被访问
    let mut y = vec![false; n]; // 记录右部点是否被访问
    let mut slack = vec![invalid; n]; // 记录松弛量
                                      // 初始化左部点的标号为与之相连的右部点的边权的最大值
    for i in 0..n {
        for j in 0..n {
            lx[i] = lx[i].max(graph[i][j]);
        }
    }
    // 在未匹配的情况下，进行增广
    while let Some(from) = (0..n).find(|i| match_[*i] == -1) {
        slack.fill(invalid); // 初始化松弛量为无穷大
        x.fill(false); // 初始化左部点为未访问
        y.fill(false); // 初始化右部点为未访问
                       // 在当前的未匹配节点进行增广
        while !dfs(
            from,
            &mut x,
            &mut y,
            &lx,
            &ly,
            &mut match_,
            &mut slack,
            graph,
        ) {
            // 如果无法找到增广路，则更新标号
            let d = slack
                .iter()
                .enumerate()
                .filter(|&(i, &s)| !y[i] && s != invalid)
                .map(|(i, _)| i)
                .min()
                .unwrap();
            for i in 0..n {
                if x[i] {
                    lx[i] -= slack[d];
                }
                if y[i] {
                    ly[i] += slack[d];
                }
            }
            x.fill(false);
            y.fill(false);
        }
    }
    // 计算所有边的权值和
    lx.iter().sum::<i32>() + ly.iter().sum::<i32>()
}

// DFS函数实现增广
fn dfs(
    from: usize,
    x: &mut [bool],
    y: &mut [bool],
    lx: &[i32],
    ly: &[i32],
    match_: &mut [i32],
    slack: &mut [i32],
    graph: &[Vec<i32>],
) -> bool {
    let n = graph.len();
    x[from] = true; // 记录左部点为已访问
    for to in 0..n {
        if !y[to] {
            // 如果右部点没有被访问
            let d = lx[from] + ly[to] - graph[from][to]; // 计算松弛量
            if d != 0 {
                // 如果松弛量不为0，则更新松弛量
                slack[to] = slack[to].min(d);
            } else {
                // 如果松弛量为0，则进行增广
                y[to] = true; // 标记右部点为已访问
                if match_[to] == -1 || dfs(match_[to] as usize, x, y, lx, ly, match_, slack, graph)
                {
                    // 如果当前右部点没有匹配，或者能够寻找到增广路，则进行匹配，并返回true
                    match_[to] = from as i32;
                    return true;
                }
            }
        }
    }
    false // 没有找到增广路，返回false
}

// 主函数
fn main() {
    // 示例数据1
    println!("{}", km(&matrix(&[2, 5, 6, 13], 4)) / 2); // 输出结果为2

    // 示例数据2
    println!("{}", km(&matrix(&[3, 6], 2)) / 2); // 输出结果为0
}

本作品采用《CC 协议》，转载必须注明作者和本文链接