难度: Medium
Submission
运行时间: 56 ms
内存: 16.8 MB
class DinicMaxflowMinCost:
def __init__(self, n):
self.n = n
self.vis = [0] * (self.n + 1)
self.point_head = [0] * (self.n + 1)
self.edge_capacity = [0] * 2
self.edge_cost = [0] * 2
self.edge_to = [0] * 2
self.edge_next = [0] * 2
self.h = [inf] * (self.n + 1)
self.dis = [inf] * (self.n + 1)
self.max_flow = 0
self.min_cost = 0
self.edge_id = 2
self.pre_edge = [0] * (self.n + 1)
self.pre_point = [0] * (self.n + 1)
def add_single_edge(self, u, v, cap, c):
self.edge_capacity.append(cap)
self.edge_cost.append(c)
self.edge_to.append(v)
self.edge_next.append(self.point_head[u])
self.point_head[u] = self.edge_id
self.edge_id += 1
return
def add_edge(self, u, v, cap, c):
self.add_single_edge(u, v, cap, c)
self.add_single_edge(v, u, 0, -c)
return
def spfa(self, s):
self.h[s] = 0
q = deque([s])
self.vis[s] = 1
while q:
u = q.popleft()
self.vis[u] = 0
i = self.point_head[u]
while i:
v = self.edge_to[i]
if self.edge_capacity[i] > 0 and self.h[v] > self.h[u] + self.edge_cost[i]:
self.h[v] = self.h[u] + self.edge_cost[i]
if not self.vis[v]:
q.append(v)
self.vis[v] = 1
i = self.edge_next[i]
return
def dijkstra(self, s, t):
for i in range(1, self.n + 1):
self.dis[i] = inf
self.vis[i] = 0
self.dis[s] = 0
q = [(0, s)]
while q:
d, u = heapq.heappop(q)
if self.vis[u]:
continue
self.vis[u] = 1
i = self.point_head[u]
while i:
v = self.edge_to[i]
nc = self.h[u] - self.h[v] + self.edge_cost[i]
if self.edge_capacity[i] > 0 and self.dis[v] > self.dis[u] + nc:
self.dis[v] = self.dis[u] + nc
self.pre_edge[v] = i
self.pre_point[v] = u
if not self.vis[v]:
heapq.heappush(q, (self.dis[v], v))
i = self.edge_next[i]
return self.dis[t] < inf
def max_flow_min_cost(self, s, t):
self.spfa(s)
while self.dijkstra(s, t):
for i in range(1, self.n + 1):
self.h[i] += self.dis[i]
cur_flow = inf
v = t
while v != s:
i = self.pre_edge[v]
c = self.edge_capacity[i]
cur_flow = cur_flow if cur_flow < c else c
v = self.pre_point[v]
v = t
while v != s:
i = self.pre_edge[v]
self.edge_capacity[i] -= cur_flow
self.edge_capacity[i ^ 1] += cur_flow
v = self.pre_point[v]
self.max_flow += cur_flow
self.min_cost += cur_flow * self.h[t]
return self.max_flow, self.min_cost
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
m, n = len(workers), len(bikes)
flow = DinicMaxflowMinCost(2 * m + 2 * n + 2)
for i in range(1, m + 1):
flow.add_edge(2 * i - 1, 2 * i, 1, 0)
flow.add_edge(2 * m + 2 * n + 1, 2 * i - 1, 1, 0)
for i in range(1, n + 1):
flow.add_edge(2 * m + 2 * i - 1, 2 * m + 2 * i, 1, 0)
flow.add_edge(2 * m + 2 * i, 2 * m + 2 * n + 2, 1, 0)
for i in range(m):
for j in range(n):
score = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
flow.add_edge(2 * (i + 1), 2 * m + 2 * (j + 1) - 1, 1, score)
ans = flow.max_flow_min_cost(2 * m + 2 * n + 1, 2 * m + 2 * n + 2)
return ans[1]
Explain
该题解通过使用最小费用最大流算法来解决校园自行车分配问题。具体地，算法创建了一个流网络，其中包括源点、汇点、工人节点和自行车节点。每个工人和自行车都分为两个节点，中间连接一条容量为1，费用为0的边，以确保每个工人和每辆自行车最多只能匹配一次。所有工人的起始点连接到源点，所有自行车的终点连接到汇点。工人到自行车的连接边的容量为1，费用为工人到自行车的曼哈顿距离。通过求解该网络的最小费用最大流，可以得到工人和自行车之间的最优分配方案。
时间复杂度: O((m+n)^2)
空间复杂度: O(m*n)
class DinicMaxflowMinCost:
def __init__(self, n):
# 初始化，n为图中节点总数
self.n = n
self.vis = [0] * (self.n + 1)
self.point_head = [0] * (self.n + 1)
self.edge_capacity = [0] * 2
self.edge_cost = [0] * 2
self.edge_to = [0] * 2
self.edge_next = [0] * 2
self.h = [inf] * (self.n + 1)
self.dis = [inf] * (self.n + 1)
self.max_flow = 0
self.min_cost = 0
self.edge_id = 2
self.pre_edge = [0] * (self.n + 1)
self.pre_point = [0] * (self.n + 1)
def add_single_edge(self, u, v, cap, c):
# 添加单向边
self.edge_capacity.append(cap)
self.edge_cost.append(c)
self.edge_to.append(v)
self.edge_next.append(self.point_head[u])
self.point_head[u] = self.edge_id
self.edge_id += 1
return
def add_edge(self, u, v, cap, c):
# 添加双向边
self.add_single_edge(u, v, cap, c)
self.add_single_edge(v, u, 0, -c)
return
def spfa(self, s):
# 使用SPFA算法计算最短路径
self.h[s] = 0
q = deque([s])
self.vis[s] = 1
while q:
u = q.popleft()
self.vis[u] = 0
i = self.point_head[u]
while i:
v = self.edge_to[i]
if self.edge_capacity[i] > 0 and self.h[v] > self.h[u] + self.edge_cost[i]:
self.h[v] = self.h[u] + self.edge_cost[i]
if not self.vis[v]:
q.append(v)
self.vis[v] = 1
i = self.edge_next[i]
return
def dijkstra(self, s, t):
# 使用Dijkstra算法进行路径优化
for i in range(1, self.n + 1):
self.dis[i] = inf
self.vis[i] = 0
self.dis[s] = 0
q = [(0, s)]
while q:
d, u = heapq.heappop(q)
if self.vis[u]:
continue
self.vis[u] = 1
i = self.point_head[u]
while i:
v = self.edge_to[i]
nc = self.h[u] - self.h[v] + self.edge_cost[i]
if self.edge_capacity[i] > 0 and self.dis[v] > self.dis[u] + nc:
self.dis[v] = self.dis[u] + nc
self.pre_edge[v] = i
self.pre_point[v] = u
if not self.vis[v]:
heapq.heappush(q, (self.dis[v], v))
i = self.edge_next[i]
return self.dis[t] < inf
def max_flow_min_cost(self, s, t):
# 主算法流程
self.spfa(s)
while self.dijkstra(s, t):
for i in range(1, self.n + 1):
self.h[i] += self.dis[i]
cur_flow = inf
v = t
while v != s:
i = self.pre_edge[v]
c = self.edge_capacity[i]
cur_flow = cur_flow if cur_flow < c else c
v = self.pre_point[v]
v = t
while v != s:
i = self.pre_edge[v]
self.edge_capacity[i] -= cur_flow
self.edge_capacity[i ^ 1] += cur_flow
v = self.pre_point[v]
self.max_flow += cur_flow
self.min_cost += cur_flow * self.h[t]
return self.max_flow, self.min_cost
class Solution:
def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
m, n = len(workers), len(bikes)
flow = DinicMaxflowMinCost(2 * m + 2 * n + 2)
for i in range(1, m + 1):
flow.add_edge(2 * i - 1, 2 * i, 1, 0)
flow.add_edge(2 * m + 2 * n + 1, 2 * i - 1, 1, 0)
for i in range(1, n + 1):
flow.add_edge(2 * m + 2 * i - 1, 2 * m + 2 * i, 1, 0)
flow.add_edge(2 * m + 2 * i, 2 * m + 2 * n + 2, 1, 0)
for i in range(m):
for j in range(n):
score = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
flow.add_edge(2 * (i + 1), 2 * m + 2 * (j + 1) - 1, 1, score)
ans = flow.max_flow_min_cost(2 * m + 2 * n + 1, 2 * m + 2 * n + 2)
return ans[1]
Explore
在构建流网络的过程中，将每个工人和每辆自行车分为两个节点并通过一条容量为1，费用为0的边相连接，这是为了确保每个工人和每辆自行车在最终的匹配中最多只能被分配一次。这样的设计允许流网络模拟“选择”过程，其中从工人的第一个节点流向第二个节点的流量表示对该工人进行了一次匹配，同样的逻辑也适用于自行车。这样可以简化流量控制，确保每个工人和自行车在匹配中的唯一性。
`self.h`数组用于存储每个节点的势能，这在计算调整后的边权重时非常关键，用以保证在每次迭代中的费用都是非负的，从而允许使用最短路径算法如Dijkstra算法。而`self.dis`数组则用于在执行Dijkstra算法时存储从源点到每个点的最短距离（考虑了势能调整后的边权重）。这两个数组是在算法寻找最小费用流的过程中，实现距离和费用更新的重要数据结构。
在最小费用流问题中，势能的引入主要是为了将原本可能包含负权重的图转换为一个仅含有非负权重的图，从而使得可以有效地应用Dijkstra算法来找到最短路径。通过势能的调整，可以保证每一次迭代过程中，所有的边权重都被调整为非负值，这是通过增加两节点间势能差与原权重的和来实现的。这种办法有效避免了在含有负权边的图中使用Dijkstra算法可能引起的问题。
势能调整后的费用`nc`的计算通过在原始费用基础上加上起点的势能并减去终点的势能来进行。这种调整的主要目的是保证所有的边权重在算法运行过程中都是非负的，从而允许使用Dijkstra算法高效地找到最短路径。通过这种势能调整，即便原始的边权重中有负值，整个算法流程仍可确保每一步都基于非负权重进行，有助于快速准确地找到成本最低的流路径。此外，这也有助于算法在每次迭代后通过更新势能，持续优化到达每个节点的最小费用，从而保证整体解决方案的最优性。