2022-06-11：注意本文件中，graph不是邻接矩阵的含义，而是一个二部图。 在长度为N的邻接矩阵matrix中，所有的点有N个，matrix[i][j]表示点i到点j的距离或者权重， 而在二部

2022-06-11：注意本文件中，graph不是邻接矩阵的含义，而是一个二部图。
在长度为N的邻接矩阵matrix中，所有的点有N个，matrix[i][j]表示点i到点j的距离或者权重，
而在二部图graph中，所有的点有2*N个，行所对应的点有N个，列所对应的点有N个。
而且认为，行所对应的点之间是没有路径的，列所对应的点之间也是没有路径的！

答案2022-06-11：

km算法。

代码用rust编写。代码如下：

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代码

2022-06-11：注意本文件中，graph不是邻接矩阵的含义，而是一个二部图。 在长度为N的邻接矩阵matrix中，所有的点有N个，matrix[i][j]表示点i到点j的距离或者权重， 而在二部的相关教程结束。