2024-01-24：用go语言，已知一个n*n的01矩阵，
只能通过通过行交换、或者列交换的方式调整矩阵，
判断这个矩阵的对角线是否能全为1，如果能返回true，不能返回false。
我们升级一下:
已知一个n*n的01矩阵，
只能通过通过行交换、或者列交换的方式调整矩阵，
判断这个矩阵的对角线是否能全为1，如果不能打印-1。
如果能，打印需要交换的次数，并且打印怎么交换。
来自网易。
答案2024-01-24：
来自左程云。
大体步骤如下：
1.遍历矩阵的每一行和每一列，统计每行和每列的1的个数。
2.如果某一行或某一列的1的个数超过n/2（n为矩阵的大小），则无法通过交换操作使得对角线上的元素全为1，直接输出-1。
3.创建一个长度为n的数组rowOnes和colOnes，分别存储每行和每列的1的个数。
4.创建一个长度为n的二维数组swap，用于记录交换操作。
5.从第一行开始，逐行遍历矩阵，对于每一行，检查是否需要进行交换：
- 如果该行的1的个数小于n/2，则说明需要进行行交换，找到一行与其交换，并更新swap数组。
6.接着从第一列开始，逐列遍历矩阵，对于每一列，检查是否需要进行交换：
- 如果该列的1的个数小于n/2且当前行没有进行过行交换，则说明需要进行列交换，找到一列与其交换，并更新swap数组。
7.最后，检查矩阵的对角线是否全为1：
- 逐行遍历矩阵，如果某一行的对角线元素不为1，则说明无法满足条件，输出-1。
8.如果能够满足条件，则输出交换次数k和交换操作：
- 遍历swap数组，输出每次交换的行号和列号。
总的时间复杂度为O(n^2)，其中n为矩阵的大小。
总的额外空间复杂度为O(n)，用于存储rowOnes、colOnes和swap数组。
go完整代码如下：
package main
import (
"fmt"
)
var out [1000][2]int
func main() {
inputs := []int{2,
0, 1,
1, 0,
2,
1, 0,
1, 0}
ii := 0
n := inputs[ii]
ii++
graph := make([][]int, n)
for i := 0; i < n; i++ {
graph[i] = make([]int, n)
for j := 0; j < n; j++ {
graph[i][j] = inputs[ii]
ii++
}
}
t := km(graph)
fmt.Println(t)
for i := 0; i < t; i++ {
fmt.Printf("R %d %d\n", out[i][0]+1, out[i][1]+1)
}
}
func km(graph [][]int) int {
N := len(graph)
lx := make([]int, N)
ly := make([]int, N)
match := make([]int, N)
x := make([]bool, N)
y := make([]bool, N)
slack := make([]int, N)
invalid := int(1e9)
for i := 0; i < N; i++ {
match[i] = -1
lx[i] = -invalid
for j := 0; j < N; j++ {
lx[i] = max(lx[i], graph[i][j])
}
ly[i] = 0
}
for from := 0; from < N; from++ {
for i := 0; i < N; i++ {
slack[i] = invalid
}
fillBoolSlice(x, false)
fillBoolSlice(y, false)
for !dfs(from, x, y, lx, ly, match, slack, graph) {
d := invalid
for i := 0; i < N; i++ {
if !y[i] && slack[i] < d {
d = slack[i]
}
}
for i := 0; i < N; i++ {
if x[i] {
lx[i] -= d
}
if y[i] {
ly[i] += d
}
}
fillBoolSlice(x, false)
fillBoolSlice(y, false)
}
}
ans := 0
for i := 0; i < N; i++ {
ans += (lx[i] + ly[i])
}
if ans < N {
return -1
}
t := 0
for i := 0; i < N; i++ {
u, v := match[i], i
if u != v {
out[t][0] = v
out[t][1] = u
for j := i + 1; j < N; j++ {
if match[j] == v {
match[j] = u
}
}
t++
}
}
return t
}
func dfs(from int, x, y []bool, lx, ly, match, slack []int, graph [][]int) bool {
N := len(graph)
x[from] = true
for to := 0; to < N; to++ {
if !y[to] {
d := lx[from] + ly[to] - graph[from][to]
if d != 0 {
slack[to] = min(slack[to], d)
} else {
y[to] = true
if match[to] == -1 || dfs(match[to], x, y, lx, ly, match, slack, graph) {
match[to] = from
return true
}
}
}
}
return false
}
func fillBoolSlice(arr []bool, value bool) {
for i := 0; i < len(arr); i++ {
arr[i] = value
}
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
python代码如下：
# -*-coding:utf-8-*-
def km(graph):
N = len(graph)
lx = [-float('inf')] * N
ly = [0] * N
match = [-1] * N
x = [False] * N
y = [False] * N
slack = [float('inf')] * N
invalid = int(1e9)
for i in range(N):
lx[i] = max(graph[i])
for from_ in range(N):
for i in range(N):
slack[i] = invalid
x = [False] * N
y = [False] * N
while not dfs(from_, x, y, lx, ly, match, slack, graph):
d = invalid
for i in range(N):
if not y[i] and slack[i] < d:
d = slack[i]
for i in range(N):
if x[i]:
lx[i] -= d
if y[i]:
ly[i] += d
x = [False] * N
y = [False] * N
ans = 0
for i in range(N):
ans += (lx[i] + ly[i])
if ans < N:
return -1
t = 0
out = [[0, 0]] * N
for i in range(N):
u, v = match[i], i
if u != v:
out[t][0] = v
out[t][1] = u
for j in range(i + 1, N):
if match[j] == v:
match[j] = u
t += 1
return t, out
def dfs(from_, x, y, lx, ly, match, slack, graph):
N = len(graph)
x[from_] = True
for to in range(N):
if not y[to]:
d = lx[from_] + ly[to] - graph[from_][to]
if d != 0:
slack[to] = min(slack[to], d)
else:
y[to] = True
if match[to] == -1 or dfs(match[to], x, y, lx, ly, match, slack, graph):
match[to] = from_
return True
return False
inputs = [2, 0, 1, 1, 0, 2, 1, 0, 1, 0]
ii = 0
n = inputs[ii]
ii += 1
graph = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
graph[i][j] = inputs[ii]
ii += 1
t, out = km(graph)
print(t)
for i in range(t):
print("R", out[i][0] + 1, out[i][1] + 1)
