若两个正整数的和为素数，则这两个正整数称之为"素数伴侣"。
给定N(偶数)个正整数中挑选出若干对，组成"素数伴侣"，
例如有4个正整数：2，5，6，13，
如果将5和6分为一组的话，只能得到一组"素数伴侣"，
如果将2和5、6和13编组，将得到两组"素数伴侣"，
这是得到"素数伴侣"最多的划分方案。
输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
输出:
输出一个整数 K ，表示最多能找出几对"素数伴侣"。
数据范围： 1 <= n <= 100, 2 <= val <= 30000。
用二分图最大匹配来解决。具体步骤如下：
将所有数字看作二分图的左右两部分节点，如果两个节点的和是一个素数，则在它们之间连接一条边。
使用 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
}
