On a campus represented as a 2D grid, there are Nworkers and Mbikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.
We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.
The Manhattan distance between two points p1and p2is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.
Example 1:
Input:
workers = [[0,0],[2,1]],
bikes = [[1,2],[3,3]]
Output: 6
Explanation:
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.
Example 2:
Input:
workers = [[0,0],[1,1],[2,0]],
bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation:
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.
class Solution(object):
def assignBikes(self, workers, bikes):
"""
:type workers: List[List[int]]
:type bikes: List[List[int]]
:rtype: int
"""
def dis(i, j):
return abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
h = [[0, 0, 0]]
seen = set()
while True:
cost, i, taken = heapq.heappop(h)
# Filter out cases (path sum) in which bikes have been assigned
if taken in seen: continue
seen.add(taken)
if i == len(workers):
return cost
for j in xrange(len(bikes)):
if taken & (1 << j) == 0:
heapq.heappush(h, [cost + dis(i,j), i + 1 , taken | (1 << j)])
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
m, n = len(workers), len(bikes)
# 0 ~ m - 1 workers
# m ~ m + n - 1 bikes
s = m + n
t = m + n + 1
num_nodes = m + n + 2
g = [[] for _ in range(num_nodes)]
prevv = [None] * num_nodes # prevv[v]: the prev node of node v
preve = [None] * num_nodes # preve[v]: the edge that connects to v: (prevv[v], v)
def add_edge(from_node, to_node, cap, cost):
g[from_node] += [[to_node, cap, cost, len(g[to_node])]] # ID for to_node's reverse edge from from_node, accessed by g[v][g[g[prevv[v]][preve[v]][3]]
g[to_node] += [[from_node, 0, -cost, len(g[from_node]) - 1]] # ID for reverse edge
# Find minimum cost to flow f from s to t
def min_cost_flow(s,t,f):
ans = 0
# Bellman-ford to expand the path
while f > 0:
# Iteratively send flow 1 to the new graph
dist = [float('inf')] * (m + n + 2)
dist[s] = 0
update = True
while update:
update = False
for v in range(num_nodes):
if dist[v] == float('inf'):
continue
# relax on v
for i, edge in enumerate(g[v]):
to_node, cap, cost, reverse_id = edge
if cap > 0 and dist[to_node] > dist[v] + cost:
dist[to_node] = dist[v] + cost
prevv[to_node] = v
preve[to_node] = i
update = True # Re-sending the flow
# update flow by decreasing the capacity of edges along the flow path
d = f
v = t
# Generic coding of flow algo
# First pass to determine the bottleneck of the flow
while v!= s:
d = min(d, g[prevv[v]][preve[v]][1])# d = 1 for this problem
v = prevv[v]
f -= d
ans += d * dist[t]# d = 1 for this problem, so actaully ans += dist[t]
# Second pass to update the capacity of the edges along the flow path
v = t
while v != s:
edge = g[prevv[v]][preve[v]]
# forward
edge[1] -=d
# residual
g[v][edge[3]][1] += d
v = prevv[v]
return ans
# Adding edges
# Source to workers: cap = 1, cost = 0
for i in range(m):
add_edge(s, i, 1, 0)
# Workers to bikes
for i in range(m):
for j in range(n):
x1, y1 = workers[i]
x2, y2 = bikes[j]
c = abs(x1 - x2) + abs(y1 - y2)
add_edge(i, j + m, 1, c)
# Bikes to sink
for j in range(n):
add_edge(j + m, t, 1, 0)
return min_cost_flow(s, t, m)
Code: DFS with early pruning:
class Solution {
int min = Integer.MAX_VALUE;
public int assignBikes(int[][] workers, int[][] bikes) {
dfs(new boolean[bikes.length], workers, 0, bikes, 0);
return min;
}
public void dfs(boolean[] visited, int[][] workers, int i, int[][]bikes, int dist){
if (i >= workers.length){
min = Math.min(dist, min);
return;
}
// Early pruning
if (dist > min){
return;
}
for(int j = 0; j < bikes.length; j++){
if(visited[j]) continue;
visited[j] = true;
dfs(visited, workers, i + 1, bikes, dist + dis(bikes[j] , workers[i]));
visited[j] = false;
}
}
public int dis(int[] p1, int [] p2){
return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}
}
Dijkstra on augmented path: vertex: states of chosen bikes, edge: Manhattan distance between worker i and bike j ()
Minimum-cost flow (): 1. Construct the graph by attaching the source and sink node along with workers and bikes node (vertex). 2. Construct the edge of the graph with capacity and cost connecting two nodes (vertices). 3. Iteratively sending flow 1 to the graph: 1. Using Bellman-ford to find the shortest path between on source and sink on current graph connection 2. Update the graph connection by augmenting path update as subtracting 1 (flow) from forward edges and add 1 for reverse edges for each node. 3. Adding the current flow cost to the answer. 4. Finally return the answer
