leetcode
leetcode 901 ~ 950
校园自行车分配 II

校园自行车分配 II

难度:

标签:

题目描述

代码结果

运行时间: 56 ms, 内存: 16.8 MB


/*
 * 思路:
 * 同样使用动态规划的方法,但利用Java Stream的特性来优化和简化代码。
 * 通过Streams进行遍历和更新,减少代码的复杂度。
 */
public int assignBikes(int[][] workers, int[][] bikes) {
    int m = workers.length, n = bikes.length;
    int[][] dp = new int[m + 1][1 << n];
    Arrays.stream(dp).forEach(arr -> Arrays.fill(arr, Integer.MAX_VALUE));
    dp[0][0] = 0;
    IntStream.range(0, m).forEach(i -> 
        IntStream.range(0, 1 << n).filter(mask -> dp[i][mask] != Integer.MAX_VALUE).forEach(mask -> 
            IntStream.range(0, n).filter(j -> (mask & (1 << j)) == 0).forEach(j -> {
                int nextMask = mask | (1 << j);
                int dist = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
                dp[i + 1][nextMask] = Math.min(dp[i + 1][nextMask], dp[i][mask] + dist);
            })
        )
    );
    return IntStream.range(0, 1 << n).map(mask -> dp[m][mask]).min().orElse(Integer.MAX_VALUE);
}

解释

方法:

该题解通过使用最小费用最大流算法来解决校园自行车分配问题。具体地,算法创建了一个流网络,其中包括源点、汇点、工人节点和自行车节点。每个工人和自行车都分为两个节点,中间连接一条容量为1,费用为0的边,以确保每个工人和每辆自行车最多只能匹配一次。所有工人的起始点连接到源点,所有自行车的终点连接到汇点。工人到自行车的连接边的容量为1,费用为工人到自行车的曼哈顿距离。通过求解该网络的最小费用最大流,可以得到工人和自行车之间的最优分配方案。

时间复杂度:

O((m+n)^2)

空间复杂度:

O(m*n)

代码细节讲解

🦆
为什么在构建流网络时,每个工人和每辆自行车都被分为两个节点,并通过一条容量为1,费用为0的边相连接?
在构建流网络的过程中,将每个工人和每辆自行车分为两个节点并通过一条容量为1,费用为0的边相连接,这是为了确保每个工人和每辆自行车在最终的匹配中最多只能被分配一次。这样的设计允许流网络模拟“选择”过程,其中从工人的第一个节点流向第二个节点的流量表示对该工人进行了一次匹配,同样的逻辑也适用于自行车。这样可以简化流量控制,确保每个工人和自行车在匹配中的唯一性。
🦆
题解中没有详细解释`self.h`和`self.dis`数组在算法中的具体作用,它们分别代表什么?
`self.h`数组用于存储每个节点的势能,这在计算调整后的边权重时非常关键,用以保证在每次迭代中的费用都是非负的,从而允许使用最短路径算法如Dijkstra算法。而`self.dis`数组则用于在执行Dijkstra算法时存储从源点到每个点的最短距离(考虑了势能调整后的边权重)。这两个数组是在算法寻找最小费用流的过程中,实现距离和费用更新的重要数据结构。
🦆
题解提到使用SPFA算法初始化势能`self.h`,请问在最小费用流问题中,势能的引入是为了解决什么问题?
在最小费用流问题中,势能的引入主要是为了将原本可能包含负权重的图转换为一个仅含有非负权重的图,从而使得可以有效地应用Dijkstra算法来找到最短路径。通过势能的调整,可以保证每一次迭代过程中,所有的边权重都被调整为非负值,这是通过增加两节点间势能差与原权重的和来实现的。这种办法有效避免了在含有负权边的图中使用Dijkstra算法可能引起的问题。
🦆
题解中的Dijkstra算法中使用了势能调整后的费用`nc`,这种调整的目的是什么,它如何影响算法找到最小费用的路径?
势能调整后的费用`nc`的计算通过在原始费用基础上加上起点的势能并减去终点的势能来进行。这种调整的主要目的是保证所有的边权重在算法运行过程中都是非负的,从而允许使用Dijkstra算法高效地找到最短路径。通过这种势能调整,即便原始的边权重中有负值,整个算法流程仍可确保每一步都基于非负权重进行,有助于快速准确地找到成本最低的流路径。此外,这也有助于算法在每次迭代后通过更新势能,持续优化到达每个节点的最小费用,从而保证整体解决方案的最优性。

相关问题

校园自行车分配

校园自行车分配