两个数组最小的异或值之和

该题解采用了最小费用最大流算法来求解最小的异或值之和。首先，定义一个流网络，其中源节点连接到数组 nums1 的每个节点，每个 nums1 的节点又与 nums2 的每个节点通过一条代表两数异或值的有向边相连，这些节点进一步连接到汇点。通过求解此网络的最小费用最大流，可以得到重新排列 nums2 后的最小异或值之和。

时间复杂度: O(n^2 * n * log n)

空间复杂度: O(n^2)

import heapq

class Edge:
    def __init__(self, from_vertex, to_vertex, capacity, cost, flow):
        # 初始化边的基本属性
        self.from_vertex = from_vertex
        self.to_vertex = to_vertex
        self.capacity = capacity
        self.cost = cost
        self.flow = flow

class MinCostMaxFlow:
    def __init__(self, total_vertices, source, sink):
        # 初始化网络流图
        self.total_vertices = total_vertices
        self.source = source
        self.sink = sink
        self.edges = []
        self.graph = [[] for _ in range(total_vertices)]
        self.distances = [float('inf')] * total_vertices
        self.flow_values = [0] * total_vertices
        self.previous = [-1] * total_vertices

    def add_edge(self, from_vertex, to_vertex, capacity, cost):
        # 向图中添加边和反向边
        self.edges.append(Edge(from_vertex, to_vertex, capacity, cost, 0))
        self.edges.append(Edge(to_vertex, from_vertex, 0, -cost, 0))
        self.graph[from_vertex].append(len(self.edges) - 2)
        self.graph[to_vertex].append(len(self.edges) - 1)

    def find_augmenting_path(self):
        # 使用优先队列实现的 Dijkstra 算法找到增广路径
        self.flow_values = [0] * self.total_vertices
        self.previous = [-1] * self.total_vertices
        self.distances = [float('inf')] * self.total_vertices
        self.distances[self.source] = 0
        self.flow_values[self.source] = float('inf')
        priority_queue = [(0, self.source)]

        while priority_queue:
            dist_u, u = heapq.heappop(priority_queue)
            if dist_u > self.distances[u]:
                continue
            for edge_index in self.graph[u]:
                edge = self.edges[edge_index]
                v = edge.to_vertex
                if edge.capacity - edge.flow > 0:
                    new_distance = self.distances[u] + edge.cost
                    if new_distance < self.distances[v]:
                        self.distances[v] = new_distance
                        self.previous[v] = edge_index
                        self.flow_values[v] = min(self.flow_values[u], edge.capacity - edge.flow)
                        heapq.heappush(priority_queue, (self.distances[v], v))

        return self.previous[self.sink] != -1

    def compute(self):
        # 计算最小费用最大流
        max_flow, min_cost = 0, 0
        while self.find_augmenting_path():
            flow = self.flow_values[self.sink]
            max_flow += flow
            min_cost += flow * self.distances[self.sink]
            current_vertex = self.sink
            while current_vertex != self.source:
                edge_index = self.previous[current_vertex]
                self.edges[edge_index].flow += flow
                self.edges[edge_index ^ 1].flow -= flow
                current_vertex = self.edges[edge_index].from_vertex
        return max_flow, min_cost

class Solution:
    def minimumXORSum(self, nums1, nums2):
        n = len(nums1)
        source = 2 * n
        sink = source + 1
        network = MinCostMaxFlow(2 * n + 2, source, sink)
        # 连接源点到 nums1 的每个顶点
        for i in range(n):
            network.add_edge(source, i, 1, 0)
        # 连接 nums1 和 nums2 的每对顶点，代价为它们的异或值
        for i in range(n):
            for j in range(n):
                cost = nums1[i] ^ nums2[j]
                network.add_edge(i, j + n, 1, cost)
        # 连接 nums2 的每个顶点到汇点
        for i in range(n):
            network.add_edge(i + n, sink, 1, 0)

        _, min_cost = network.compute()
        return min_cost