# ===== BEGIN: /Suzlib/python/graph/BipartiteMatching.py ===== # competitive-verifier: TITLE 最大二部マッチング from random import shuffle class BipartiteMatching: """Kuhn 法を前処理に用いた Hopcroft--Karp 法。初回 solve の計算量は O((V + E) sqrt(V))。 辺番号を維持するため、削除済み辺も内部に保持する。 累積追加辺数を A とすると、辺情報の保持には O(A) の空間を使い、 edges は O(A)、matching_edge_ids は solve 後に O(V + A)、 CSR の再構築は O(V + A) 時間を要する。 """ def __init__(self, n_left: int, n_right: int) -> None: """左右の頂点数を設定し、辺のない二部グラフと空のマッチングを作る。""" assert 0 <= n_left assert 0 <= n_right self.n_left = n_left self.n_right = n_right self.g: list[list[int]] | None = None self.mate_left = [-1] * n_left self.mate_right = [-1] * n_right self.size = 0 self._edge_shift = max(1, (n_right - 1).bit_length()) self._edge_mask = (1 << self._edge_shift) - 1 self._edges: list[int] = [] self._removed_edges: set[int] = set() self._start: list[int] = [] self._to: list[int] = [] self._csr_built = False self._solved = False def add_edge(self, left: int, right: int) -> int: """solve 前に左頂点 left と右頂点 right を結ぶ辺を追加し、辺番号を返す。""" if self._solved: raise RuntimeError("call add_edge() before solve()") assert 0 <= left < self.n_left assert 0 <= right < self.n_right edge_id = len(self._edges) self._edges.append((left << self._edge_shift) | right) return edge_id def edge_count(self) -> int: """これまでに発行した辺番号の個数を返す。削除済み辺も数える。""" return len(self._edges) def edges(self) -> list[tuple[int, int, int]]: """現在存在する辺を (edge_id, left, right) で返す。""" shift = self._edge_shift mask = self._edge_mask removed = self._removed_edges return [ (edge_id, edge >> shift, edge & mask) for edge_id, edge in enumerate(self._edges) if edge_id not in removed ] def _build_csr(self) -> None: """現在の辺を左頂点ごとの CSR にまとめる。再構築は累積追加辺数 A に対し O(V + A)。""" if self._csr_built: return removed = self._removed_edges if removed: edges = [ edge for edge_id, edge in enumerate(self._edges) if edge_id not in removed ] else: edges = self._edges.copy() shuffle(edges) shift = self._edge_shift mask = self._edge_mask start = [0] * (self.n_left + 1) for edge in edges: start[(edge >> shift) + 1] += 1 for left in range(self.n_left): start[left + 1] += start[left] to = [0] * len(edges) pos = start[:-1] for edge in edges: left = edge >> shift to[pos[left]] = edge & mask pos[left] += 1 self._start = start self._to = to self._csr_built = True def _materialize_adjacency(self) -> None: """更新操作のため、必要になった時だけ可変な隣接リストを生成する。""" if self.g is not None: return self._build_csr() start = self._start to = self._to self.g = [ to[start[left]:start[left + 1]] for left in range(self.n_left) ] def _degree_greedy(self) -> int: """左右両側の CSR を用いて低次数頂点を優先した初期マッチングを構成する。""" start = self._start to = self._to mate_left = self.mate_left mate_right = self.mate_right n_left = self.n_left n_right = self.n_right rstart = [0] * (n_right + 1) for right in to: rstart[right + 1] += 1 for right in range(n_right): rstart[right + 1] += rstart[right] rto = [0] * len(to) pos = rstart[:-1] for left in range(n_left): for i in range(start[left], start[left + 1]): right = to[i] rto[pos[right]] = left pos[right] += 1 degree_left = [start[left + 1] - start[left] for left in range(n_left)] degree_right = [rstart[right + 1] - rstart[right] for right in range(n_right)] leaves = [left for left in range(n_left) if degree_left[left] == 1] leaves += [n_left + right for right in range(n_right) if degree_right[right] == 1] twos = [left for left in range(n_left) if degree_left[left] == 2] twos += [n_left + right for right in range(n_right) if degree_right[right] == 2] added = 0 scan = 0 m = len(to) while True: while leaves: v = leaves[-1] degree = degree_left[v] if v < n_left else degree_right[v - n_left] if degree == 1: break leaves.pop() if leaves: v = leaves.pop() if v < n_left: left = v right = -1 for i in range(start[left], start[left + 1]): w = to[i] if degree_right[w]: right = w break else: right = v - n_left left = -1 for i in range(rstart[right], rstart[right + 1]): w = rto[i] if degree_left[w]: left = w break else: while scan < n_left and degree_left[scan] == 0: scan += 1 if scan == n_left: break while twos: v = twos[-1] degree = degree_left[v] if v < n_left else degree_right[v - n_left] if degree == 2: break twos.pop() v = twos.pop() if twos else scan if v < n_left: left = v right = -1 best = m + 1 for i in range(start[left], start[left + 1]): w = to[i] degree = degree_right[w] if 0 < degree < best: right = w best = degree else: right = v - n_left left = -1 best = m + 1 for i in range(rstart[right], rstart[right + 1]): w = rto[i] degree = degree_left[w] if 0 < degree < best: left = w best = degree if left == -1 or right == -1: continue mate_left[left] = right mate_right[right] = left added += 1 degree_left[left] = 0 degree_right[right] = 0 for i in range(start[left], start[left + 1]): w = to[i] if degree_right[w]: degree_right[w] -= 1 if degree_right[w] == 1: leaves.append(n_left + w) elif degree_right[w] == 2: twos.append(n_left + w) for i in range(rstart[right], rstart[right + 1]): w = rto[i] if degree_left[w]: degree_left[w] -= 1 if degree_left[w] == 1: leaves.append(w) elif degree_left[w] == 2: twos.append(w) return added def solve(self) -> int: """現在のグラフの最大マッチング数を返す。""" if self._solved: return self.size self._build_csr() start = self._start to = self._to mate_left = self.mate_left mate_right = self.mate_right if self.size == 0: self.size = self._degree_greedy() if self.size == 0: self._solved = True return 0 if self.size == min(self.n_left, self.n_right): self._solved = True return self.size parent = [-1] * self.n_left root = [-1] * self.n_left queue = [0] * self.n_left def kuhn_phase() -> int: """全未マッチ左頂点から交互森を伸ばし、増大路を貪欲に反転する。""" q_tail = 0 for left in range(self.n_left): parent[left] = -1 if mate_left[left] == -1: parent[left] = -2 root[left] = left queue[q_tail] = left q_tail += 1 added = 0 q_front = 0 while q_front < q_tail: left = queue[q_front] q_front += 1 if mate_left[root[left]] != -1: continue matched_right = mate_left[left] for i in range(start[left], start[left + 1]): right = to[i] if right == matched_right: continue next_left = mate_right[right] if next_left == -1: while left >= 0: mate_right[right] = left right, mate_left[left] = mate_left[left], right left = parent[left] added += 1 break if parent[next_left] == -1: parent[next_left] = left root[next_left] = root[left] queue[q_tail] = next_left q_tail += 1 return added for _ in range(128): added = kuhn_phase() self.size += added if added == 0 or self.size == min(self.n_left, self.n_right): self._solved = True return self.size del parent, root, queue inf = self.n_left + 1 dist = [inf] * self.n_left current_edge: list[int] = [] def bfs() -> int: """未マッチ左頂点から BFS し、最短増大路の長さを返す。""" queue: list[int] = [] for left in range(self.n_left): if mate_left[left] == -1: dist[left] = 0 queue.append(left) else: dist[left] = inf q_front = 0 while q_front < len(queue): left = queue[q_front] q_front += 1 next_dist = dist[left] + 1 for i in range(start[left], start[left + 1]): right = to[i] next_left = mate_right[right] if next_left == -1: return next_dist if dist[next_left] == inf: dist[next_left] = next_dist queue.append(next_left) return inf def dfs(start_left: int, shortest: int) -> bool: """BFS 層に沿って最短増大路を1本探し、見つかれば反転する。""" left = start_left left_stack: list[int] = [] while True: i = current_edge[left] end = start[left + 1] target = dist[left] + 1 while i < end: right = to[i] i += 1 next_left = mate_right[right] if next_left == -1: if target != shortest: continue current_edge[left] = i while True: mate_right[right] = left right, mate_left[left] = mate_left[left], right if right == -1: return True left = left_stack.pop() if dist[next_left] == target: current_edge[left] = i left_stack.append(left) left = next_left break else: current_edge[left] = i dist[left] = inf if not left_stack: return False left = left_stack.pop() while True: shortest = bfs() if shortest == inf: break current_edge = start[:-1] for left in range(self.n_left): if mate_left[left] == -1 and dfs(left, shortest): self.size += 1 self._solved = True return self.size def _augment_once(self) -> bool: """全ての未マッチ左頂点から交互 BFS を1回だけ行い、増大路を1本だけ反転する。""" self._materialize_adjacency() assert self.g is not None g = self.g mate_left = self.mate_left mate_right = self.mate_right queue: list[int] = [] parent = [-1] * self.n_left seen = [False] * self.n_left for left in range(self.n_left): if mate_left[left] == -1: seen[left] = True queue.append(left) q_front = 0 while q_front < len(queue): left = queue[q_front] q_front += 1 matched_right = mate_left[left] for right in g[left]: if right == matched_right: continue next_left = mate_right[right] if next_left == -1: while right != -1: mate_right[right] = left right, mate_left[left] = mate_left[left], right left = parent[left] self.size += 1 return True if not seen[next_left]: seen[next_left] = True parent[next_left] = left queue.append(next_left) return False def increment_edge(self, left: int, right: int) -> bool: """最大マッチング構築後に辺を1本追加し、サイズが増えたかを返す。""" if not self._solved: raise RuntimeError("call solve() before increment_edge()") assert 0 <= left < self.n_left assert 0 <= right < self.n_right self._materialize_adjacency() assert self.g is not None self._edges.append((left << self._edge_shift) | right) self.g[left].append(right) self._csr_built = False if self.size == min(self.n_left, self.n_right): return False if self.mate_left[left] == -1 and self.mate_right[right] == -1: self.mate_left[left] = right self.mate_right[right] = left self.size += 1 return True return self._augment_once() def increment_edges_from_left(self, left: int, rights: list[int]) -> bool: """最大マッチング構築後に一つの左頂点から複数辺を追加し、サイズが増えたかを返す。""" if not self._solved: raise RuntimeError("call solve() before increment_edges_from_left()") assert 0 <= left < self.n_left for right in rights: assert 0 <= right < self.n_right self._materialize_adjacency() assert self.g is not None base = left << self._edge_shift self._edges.extend(base | right for right in rights) self.g[left].extend(rights) self._csr_built = False if self.size == min(self.n_left, self.n_right): return False if self.mate_left[left] == -1: for right in rights: if self.mate_right[right] == -1: self.mate_left[left] = right self.mate_right[right] = left self.size += 1 return True return self._augment_once() def increment_edges_from_right(self, right: int, lefts: list[int]) -> bool: """最大マッチング構築後に一つの右頂点へ複数辺を追加し、サイズが増えたかを返す。""" if not self._solved: raise RuntimeError("call solve() before increment_edges_from_right()") assert 0 <= right < self.n_right for left in lefts: assert 0 <= left < self.n_left self._materialize_adjacency() assert self.g is not None for left in lefts: self._edges.append((left << self._edge_shift) | right) self.g[left].append(right) self._csr_built = False if self.size == min(self.n_left, self.n_right): return False if self.mate_right[right] == -1: for left in lefts: if self.mate_left[left] == -1: self.mate_left[left] = right self.mate_right[right] = left self.size += 1 return True return self._augment_once() def remove_edge(self, edge_id: int) -> bool: """最大マッチング構築後に辺番号 edge_id の辺を削除し、最大マッチング数が減ったかを返す。""" if not self._solved: raise RuntimeError("call solve() before remove_edge()") assert 0 <= edge_id < len(self._edges) if edge_id in self._removed_edges: raise ValueError("edge is already removed") self._materialize_adjacency() assert self.g is not None edge = self._edges[edge_id] left = edge >> self._edge_shift right = edge & self._edge_mask self._removed_edges.add(edge_id) self.g[left].remove(right) self._csr_built = False if self.mate_left[left] != right: return False self.mate_left[left] = -1 self.mate_right[right] = -1 self.size -= 1 return not self._augment_once() def matching_edges(self) -> list[tuple[int, int]]: """最大マッチングに使われる (左頂点, 右頂点) を返す。""" self.solve() return [ (left, right) for left, right in enumerate(self.mate_left) if right != -1 ] def matching_edge_ids(self) -> list[int]: """最大マッチングに対応する入力辺番号を返す。多重辺では最初の辺を選ぶ。""" self.solve() edge_for_left = [-1] * self.n_left shift = self._edge_shift mask = self._edge_mask removed = self._removed_edges for edge_id, edge in enumerate(self._edges): if edge_id in removed: continue left = edge >> shift if edge_for_left[left] != -1: continue right = edge & mask if self.mate_left[left] == right: edge_for_left[left] = edge_id return [edge_id for edge_id in edge_for_left if edge_id != -1] def mates(self) -> tuple[list[int], list[int]]: """左から右、右から左への対応をそれぞれ返す。未対応は -1。""" self.solve() return self.mate_left.copy(), self.mate_right.copy() def residual_graph(self, middle_capacity_inf: bool = False) -> list[list[int]]: """ 最大マッチングを s -> left -> right -> t のフローと見た残余グラフを返す。 頂点番号は左 0..n_left-1、右 n_left..n_left+n_right-1、 s = n_left+n_right、t = s+1 とする。 middle_capacity_inf=True なら left -> right の容量を inf とみなす。 """ self.solve() n_left = self.n_left n_right = self.n_right s = n_left + n_right t = s + 1 g = [[] for _ in range(t + 1)] for left, right in enumerate(self.mate_left): if right == -1: g[s].append(left) else: g[left].append(s) matched = set(self.matching_edge_ids()) for edge_id, left, right in self.edges(): r = n_left + right if middle_capacity_inf or edge_id not in matched: g[left].append(r) if edge_id in matched: g[r].append(left) for right, left in enumerate(self.mate_right): r = n_left + right if left == -1: g[r].append(t) else: g[t].append(r) return g def _reachable_sets(self) -> tuple[list[bool], list[bool]]: """未マッチ左頂点から交互路で到達可能な左右の頂点集合を返す。""" self.solve() self._build_csr() start = self._start to = self._to seen_left = [False] * self.n_left seen_right = [False] * self.n_right queue: list[int] = [] for left in range(self.n_left): if self.mate_left[left] == -1: seen_left[left] = True queue.append(left) q_front = 0 while q_front < len(queue): left = queue[q_front] q_front += 1 matched_right = self.mate_left[left] for i in range(start[left], start[left + 1]): right = to[i] if right == matched_right or seen_right[right]: continue seen_right[right] = True next_left = self.mate_right[right] if next_left != -1 and not seen_left[next_left]: seen_left[next_left] = True queue.append(next_left) return seen_left, seen_right def min_vertex_cover(self) -> tuple[list[int], list[int]]: """最小頂点被覆を (左頂点列, 右頂点列) で返す。""" seen_left, seen_right = self._reachable_sets() left = [v for v in range(self.n_left) if not seen_left[v]] right = [v for v in range(self.n_right) if seen_right[v]] return left, right def max_independent_set(self) -> tuple[list[int], list[int]]: """最大独立集合を (左頂点列, 右頂点列) で返す。""" seen_left, seen_right = self._reachable_sets() left = [v for v in range(self.n_left) if seen_left[v]] right = [v for v in range(self.n_right) if not seen_right[v]] return left, right class GeneralBipartiteMatching: """頂点を一つの整数空間で与え、自動で二部彩色する最大二部マッチング。""" def __init__(self, n: int) -> None: """n 頂点の空の辺列と、未彩色・未マッチの状態を初期化する。""" assert 0 <= n self.n = n self.edges: list[tuple[int, int]] = [] self.color = [-1] * n self.toL = [-1] * n self.toR = [-1] * n self.fromL: list[int] = [] self.fromR: list[int] = [] self.mateL: list[int] = [] self.mateR: list[int] = [] self.mate = [-1] * n self.size = 0 self._matching: BipartiteMatching | None = None self._solved = False def add_edge(self, u: int, v: int) -> int: """頂点 u, v を結ぶ辺を追加し、辺番号を返す。solve 後は彩色を含めて再構築する。""" assert 0 <= u < self.n assert 0 <= v < self.n edge_id = len(self.edges) self.edges.append((u, v)) self._solved = False return edge_id def _bipartition(self) -> None: """現在の辺集合を二部彩色し、各頂点の色を self.color に保存する。""" graph = [[] for _ in range(self.n)] for u, v in self.edges: graph[u].append(v) graph[v].append(u) color = [-1] * self.n for start in range(self.n): if color[start] != -1: continue color[start] = 1 queue = [start] q_front = 0 while q_front < len(queue): u = queue[q_front] q_front += 1 next_color = color[u] ^ 1 for v in graph[u]: if color[v] == -1: color[v] = next_color queue.append(v) elif color[v] != next_color: raise ValueError("graph is not bipartite") self.color = color def _build_lr(self) -> None: """二部彩色を左右に圧縮し、内部の BipartiteMatching を構築する。""" self._bipartition() self.fromL = [v for v in range(self.n) if self.color[v] == 0] self.fromR = [v for v in range(self.n) if self.color[v] == 1] self.toL = [-1] * self.n self.toR = [-1] * self.n for left, v in enumerate(self.fromL): self.toL[v] = left for right, v in enumerate(self.fromR): self.toR[v] = right matching = BipartiteMatching(len(self.fromL), len(self.fromR)) packed_edges: list[int] = [] shift = matching._edge_shift for u, v in self.edges: if self.color[u] == 0: left = self.toL[u] right = self.toR[v] else: left = self.toL[v] right = self.toR[u] packed_edges.append((left << shift) | right) matching._edges = packed_edges self._matching = matching def solve(self) -> int: """現在のグラフの最大マッチング数を返す。非二部グラフなら ValueError。""" if self._solved: return self.size self._build_lr() assert self._matching is not None self.size = self._matching.solve() self.mateL = self._matching.mate_left self.mateR = self._matching.mate_right self.mate = [-1] * self.n for left, right in enumerate(self.mateL): if right == -1: continue u = self.fromL[left] v = self.fromR[right] self.mate[u] = v self.mate[v] = u self._solved = True return self.size def matching_edges(self) -> list[tuple[int, int]]: """最大マッチングを (色0の頂点, 色1の頂点) の組で返す。""" self.solve() return [ (self.fromL[left], self.fromR[right]) for left, right in enumerate(self.mateL) if right != -1 ] def matching_edge_ids(self) -> list[int]: """最大マッチングに対応する入力辺番号を返す。多重辺では最初の辺を選ぶ。""" self.solve() assert self._matching is not None return self._matching.matching_edge_ids() def mates(self) -> list[int]: """各頂点の対応先を返す。未対応は -1。""" self.solve() return self.mate.copy() def residual_graph(self, middle_capacity_inf: bool = False) -> list[list[int]]: """ 自動二部彩色で color 0 を左、color 1 を右とした残余グラフを返す。 頂点番号は入力時の 0..n-1 を保ち、s = n、t = n+1 とする。 middle_capacity_inf=True なら左から右への容量を inf とみなす。 """ self.solve() assert self._matching is not None rg = self._matching.residual_graph(middle_capacity_inf) original = self.fromL + self.fromR internal_s = self.n internal_t = self.n + 1 original += [internal_s, internal_t] g = [[] for _ in range(self.n + 2)] for v, adj in enumerate(rg): g[original[v]] = [original[w] for w in adj] return g def min_vertex_cover(self) -> list[int]: """元の頂点番号で最小頂点被覆を返す。""" self.solve() assert self._matching is not None left, right = self._matching.min_vertex_cover() return [self.fromL[v] for v in left] + [self.fromR[v] for v in right] def max_independent_set(self) -> list[int]: """元の頂点番号で最大独立集合を返す。""" self.solve() assert self._matching is not None left, right = self._matching.max_independent_set() return [self.fromL[v] for v in left] + [self.fromR[v] for v in right] # ===== END: /Suzlib/python/graph/BipartiteMatching.py ===== import sys readline = sys.stdin.readline # T = int(readline()) # for _ in range(T): # ans = solve() # print(ans) # n = int(readline()) # a = [int(i) for i in readline().split()] # ab = [[int(i) for i in readline().split()] for _ in range()] # S = readline().strip() # b = [readline().strip() for _ in range()] def solve(n,R,C): if n == 2: return None b = [[v]*n for v in R] x = C[0] if all(v == x for v in C): # 全部同じなら、ダメなことがある if n <= 4: return None j = 0 for i in range(n): while b[j][i] == x: j += 1 if j >= n: j = 0 b[j][i] = x j += 1 if j >= n: j = 0 return b # そうでないならマッチング可能 g = BipartiteMatching(n,n) for i in range(n): for j in range(n): if R[i] != C[j]: g.add_edge(i,j) g.solve() lst = g.matching_edges() for v,w in lst: b[v][w] = C[w] #print(lst) return b T = int(readline()) for _ in range(T): n = int(readline()) R = [int(i) for i in readline().split()] C = [int(i) for i in readline().split()] ans = solve(n,R,C) if not ans: print(-1) else: for lst in ans: print(*lst)