本文共 2442 字，大约阅读时间需要 8 分钟。
为了解决这个问题，我们需要判断是否可以通过行和列交换，使得一个N×N的二进制矩阵的主对角线全部为黑色（即1）。这个问题可以通过构建二分图并寻找完美匹配来解决。
import sysfrom collections import dequedef main(): input = sys.stdin.read().split() ptr = 0 T = int(input[ptr]) ptr += 1 for _ in range(T): N = int(input[ptr]) ptr += 1 grid = [] for i in range(N): row = list(map(int, input[ptr:ptr+N])) ptr += N grid.append(row) # Construct bipartite graph adj = [[] for _ in range(N+1)] # 1-based indexing for rows and columns for i in range(N): for j in range(N): if grid[i][j] == 1: adj[i+1].append(j+1) # Hopcroft-Karp algorithm pair_u = [0] * (N + 1) pair_v = [0] * (N + 1) dist = [0] * (N + 1) result = 0 def bfs(): queue = deque() for u in range(1, N+1): if pair_u[u] == 0: dist[u] = 0 queue.append(u) else: dist[u] = float('inf') dist[0] = float('inf') while queue: u = queue.popleft() if u != 0: for v in adj[u]: if dist[pair_v[v]] == float('inf'): dist[pair_v[v]] = dist[u] + 1 queue.append(pair_v[v]) return dist[0] != float('inf') def dfs(u): if u != 0: for v in adj[u]: if dist[pair_v[v]] == dist[u] + 1: if dfs(pair_v[v]): pair_u[u] = v pair_v[v] = u return True dist[u] = float('inf') return False return True while bfs(): for u in range(1, N+1): if pair_u[u] == 0: if dfs(u): result += 1 if result == N: print("Yes") else: print("No")if __name__ == "__main__": main() 通过这种方法，我们可以高效地判断矩阵是否可以通过行和列交换使主对角线全部为黑色。
转载地址：http://xdmu.baihongyu.com/