该题解使用了网络流的最小费用最大流算法来解决问题。首先，构建一个图，其中包含一个源点和一个汇点，以及代表数字和篮子的节点。为每个数字到每个篮子的边设置一个容量为无穷大，费用为该数字与篮子编号的按位与的负值。这样设置费用是为了最小费用流算法能求得最大与和。同时，将所有数字连接到源点的边的容量设为1，费用设为0，意味着每个数字只能选择一个篮子。每个篮子到汇点的边的容量设置为2，费用为0，表示每个篮子最多只能放两个数字。通过不断找到一条从源点到汇点的最小费用的路径并增加流量，直到没有增广路径存在，计算总的最小费用，并将其转化为最大与和。
时间复杂度: O(V^2*E)
空间复杂度: O(V + E)
from collections import deque
class Edge:
def __init__(self, to, rev, cap, cost):
# 初始化边，包含终点、反向边索引、容量和费用
self.to = to
self.rev = rev
self.cap = cap
self.cost = cost
def add_edge(graph, from_, to, cap, cost):
# 向图中添加边
graph[from_].append(Edge(to, len(graph[to]), cap, cost))
graph[to].append(Edge(from_, len(graph[from_]-1), 0, -cost))
def spfa(graph, start, end, dist, parent):
# SPFA算法寻找最小费用路径
inf = 10**9
for i in range(len(dist)):
dist[i] = inf
dist[start] = 0
in_queue = [False] * len(graph)
in_queue[start] = True
queue = deque([start])
while queue:
v = queue.popleft()
in_queue[v] = False
for i, edge in enumerate(graph[v]):
if edge.cap > 0 and dist[v] + edge.cost < dist[edge.to]:
dist[edge.to] = dist[v] + edge.cost
parent[edge.to] = (v, i)
if not in_queue[edge.to]:
queue.append(edge.to)
in_queue[edge.to] = True
return dist[end] != inf
class Solution:
def maximumANDSum(self, nums, num_slots):
# 初始化图和变量
n, m = len(nums), num_slots
graph = [[] for _ in range(n + m + 2)]
start, end = n + m, n + m + 1
inf = 10**9
# 添加边
for i, num in enumerate(nums):
add_edge(graph, start, i, 1, 0)
for j in range(1, m + 1):
add_edge(graph, i, n + j - 1, inf, -(num & j))
for i in range(m):
add_edge(graph, n + i, end, 2, 0)
# 最小费用最大流主循环
ans = 0
dist = [0] * len(graph)
parent = [None] * len(graph)
while spfa(graph, start, end, dist, parent):
min_flow = inf
v = end
while v != start:
p, i = parent[v]
min_flow = min(min_flow, graph[p][i].cap)
v = p
v = end
while v != start:
p, i = parent[v]
graph[p][i].cap -= min_flow
graph[v][graph[p][i].rev].cap += min_flow
v = p
ans -= dist[end] * min_flow
return ans