2022-06-11：注意本文件中，graph不是邻接矩阵的含义，而是一个二部图。
在长度为N的邻接矩阵matrix中，所有的点有N个，matrix[i][j]表示点i到点j的距离或者权重，
而在二部图graph中，所有的点有2*N个，行所对应的点有N个，列所对应的点有N个。
而且认为，行所对应的点之间是没有路径的，列所对应的点之间也是没有路径的！
答案2022-06-11：
km算法。
代码用rust编写。代码如下：
代码语言：javascript复制use rand::Rng;
fn main() {
let n: i32 = 10;
let v: i32 = 20;
let test_time: i32 = 10;
println!("测试开始");
for _ in 0..test_time {
let mut graph = random_graph(n, v);
let ans1 = right(&mut graph);
let ans2 = km(&mut graph);
if ans1 != ans2 {
println!("出错了!");
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
println!("===============");
}
}
println!("测试结束");
}
// 暴力解
fn right(graph: &mut Vec<Vec<i32>>) -> i32 {
let N = graph.len() as i32;
let mut to: Vec<i32> = vec![];
for _ in 0..N {
to.push(1);
}
return process(0, &mut to, graph);
}
fn process(from: i32, to: &mut Vec<i32>, graph: &mut Vec<Vec<i32>>) -> i32 {
if from == graph.len() as i32 {
return 0;
}
let mut ans = 0;
for i in 0..to.len() as i32 {
if to[i as usize] == 1 {
to[i as usize] = 0;
ans = get_max(
ans,
graph[from as usize][i as usize] process(from 1, to, graph),
);
to[i as usize] = 1;
}
}
return ans;
}
fn get_max<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn get_min<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
fn km(graph: &mut Vec<Vec<i32>>) -> i32 {
let N = graph.len() as i32;
let mut match0: Vec<i32> = vec![];
let mut lx: Vec<i32> = vec![];
let mut ly: Vec<i32> = vec![];
// dfs过程中，碰过的点！
let mut x: Vec<bool> = vec![];
let mut y: Vec<bool> = vec![];
// 降低的预期！
// 公主上，打一个，降低预期的值，只维持最小！
let mut slack: Vec<i32> = vec![];
let mut falsev: Vec<bool> = vec![];
for _ in 0..N {
match0.push(0);
lx.push(0);
ly.push(0);
x.push(false);
y.push(false);
slack.push(0);
falsev.push(false);
}
let invalid = 2147483647;
for i in 0..N {
match0[i as usize] = -1;
lx[i as usize] = -invalid;
for j in 0..N {
lx[i as usize] = get_max(lx[i as usize], graph[i as usize][j as usize]);
}
ly[i as usize] = 0;
}
for from in 0..N {
for i in 0..N {
slack[i as usize] = invalid;
}
x = falsev.clone();
y = falsev.clone();
// dfs() : from王子，能不能不降预期，匹配成功！
// 能：dfs返回true！
// 不能：dfs返回false！
while !dfs(
from,
&mut x,
&mut y,
&mut lx,
&mut ly,
&mut match0,
&mut slack,
graph,
) {
// 刚才的dfs，失败了！
// 需要拿到，公主的slack里面，预期下降幅度的最小值！
let mut d = invalid;
for i in 0..N {
if !y[i as usize] && slack[i as usize] < d {
d = slack[i as usize];
}
}
// 按照最小预期来调整预期
for i in 0..N {
if x[i as usize] {
lx[i as usize] = lx[i as usize] - d;
}
if y[i as usize] {
ly[i as usize] = ly[i as usize] d;
}
}
x = falsev.clone();
y = falsev.clone();
// 然后回到while里，再次尝试
}
}
let mut ans = 0;
for i in 0..N {
ans = lx[i as usize] ly[i as usize];
}
return ans;
}
// from, 当前的王子
// x，王子碰没碰过
// y, 公主碰没碰过
// lx，所有王子的预期
// ly, 所有公主的预期
// match，所有公主，之前的分配，之前的爷们！
// slack，连过，但没允许的公主，最小下降的幅度
// map，报价，所有王子对公主的报价
// 返回，from号王子，不降预期能不能配成！
fn dfs(
from: i32,
x: &mut Vec<bool>,
y: &mut Vec<bool>,
lx: &mut Vec<i32>,
ly: &mut Vec<i32>,
match0: &mut Vec<i32>,
slack: &mut Vec<i32>,
map: &mut Vec<Vec<i32>>,
) -> bool {
let N = map.len() as i32;
x[from as usize] = true;
for to in 0..N {
if !y[to as usize] {
// 只有没dfs过的公主，才会去尝试
let d = lx[from as usize] ly[to as usize] - map[from as usize][to as usize];
if d != 0 {
// 如果当前的路不符合预期，更新公主的slack值
slack[to as usize] = get_min(slack[to as usize], d);
} else {
// 如果当前的路符合预期，尝试直接拿下，或者抢夺让之前的安排倒腾去
y[to as usize] = true;
if match0[to as usize] == -1
|| dfs(match0[to as usize], x, y, lx, ly, match0, slack, map)
{
match0[to as usize] = from;
return true;
}
}
}
}
return false;
}
// 为了测试
fn random_graph(N: i32, V: i32) -> Vec<Vec<i32>> {
let mut graph: Vec<Vec<i32>> = vec![];
for i in 0..N {
graph.push(vec![]);
for _ in 0..N {
graph[i as usize].push(0);
}
}
for i in 0..N {
for j in i 1..N {
let num = rand::thread_rng().gen_range(0, V);
graph[i as usize][j as usize] = num;
graph[j as usize][i as usize] = num;
}
}
return graph;
}执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_03_5_week/Code01_KMAlgorithm.java)
