2022-06-11: note that in this document, graph is not the meaning of adjacency matrix, but a bipartite graph. In the adjacency matrix with length N, there are n points, matrix[i][j]

2022-06-11： Note in this document ,graph Not the meaning of adjacency matrix , It's a bipartite graph .

In the length of N The adjacency matrix of matrix in , All the points are N individual ,matrixi Indication point i point-to-point j Distance or weight of ,

And in the bipartite graph graph in , All the points are 2*N individual , The points corresponding to the row are N individual , The points corresponding to the column are N individual .

And think , There is no path between the points corresponding to the row , There is also no path between the points corresponding to the column ！

answer 2022-06-11：

km Algorithm .

The code to use rust To write . The code is as follows ：

use rand::Rng;
fn main() {
    let n: i32 = 10;
    let v: i32 = 20;
    let test_time: i32 = 10;
    println!(" Beginning of the test ");
    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!(" Something went wrong !");
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            println!("===============");
        }
    }
    println!(" End of test ");
}

//  Violent solution 
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 In the process , Touched points ！
    let mut x: Vec<bool> = vec![];
    let mut y: Vec<bool> = vec![];
    //  Lowered expectations ！
    //  Princess , Make a , Lower the expected value , Keep it to a minimum ！
    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 prince , Can we not lower our expectations , The match is successful ！
        //  can ：dfs return true！
        //  You can't ：dfs return false！
        while !dfs(
            from,
            &mut x,
            &mut y,
            &mut lx,
            &mut ly,
            &mut match0,
            &mut slack,
            graph,
        ) {
            //  Just now dfs, failed ！
            //  Need to get , Princess's slack Inside , The minimum value of the expected decrease ！
            let mut d = invalid;
            for i in 0..N {
                if !y[i as usize] && slack[i as usize] < d {
                    d = slack[i as usize];
                }
            }
            //  Adjust the expectation according to the minimum expectation 
            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();
            //  Then back while in , Try it again 
        }
    }
    let mut ans = 0;
    for i in 0..N {
        ans += lx[i as usize] + ly[i as usize];
    }
    return ans;
}

// from,  The current Prince 
// x, Did the prince touch it 
// y,  Did the princess touch it 
// lx, All the prince's expectations 
// ly,  All the princess's expectations 
// match, All the princesses , Previous assignments , Men before ！
// slack, Continuous , But the princess without permission , The minimum decrease 
// map, offer , All the prince's offers to the princess 
//  return ,from Prince No , Do not lower expectations can match ！
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] {
            //  Only No dfs The princess who passed , To try 
            let d = lx[from as usize] + ly[to as usize] - map[from as usize][to as usize];
            if d != 0 {
                //  If the current road does not meet expectations , Update the princess's slack value 
                slack[to as usize] = get_min(slack[to as usize], d);
            } else {
                //  If the current road meets expectations , Try to take it directly , Or grab and let the previous arrangement go upside down 
                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;
}

//  In order to test 
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;
}

Copy

The results are as follows ：

Insert picture description here

---

Zuo Shen java Code