2024-01-24：用go语言，已知一个n*n的01矩阵， 只能通过通过行交换、或者列交换的方式调整矩阵， 判断这个矩阵的对角线是否能全为1，如果能返回true，不能返回false。 我们升级一下:

2024-01-24：用go语言，已知一个n*n的01矩阵，

只能通过通过行交换、或者列交换的方式调整矩阵，

判断这个矩阵的对角线是否能全为1，如果能返回true，不能返回false。

我们升级一下:

已知一个n*n的01矩阵，

只能通过通过行交换、或者列交换的方式调整矩阵，

判断这个矩阵的对角线是否能全为1，如果不能打印-1。

如果能，打印需要交换的次数，并且打印怎么交换。

来自网易。

答案2024-01-24：

来自左程云。

灵捷3.5

大体步骤如下：

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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86