java 解法, 执行用时: 28 ms, 内存消耗: 70.2 MB, 提交时间: 2024-10-13 23:41:07

class Solution {
    public long maximumValueSum(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][][] suf = new int[m][3][2];
        int[][] p = new int[3][2]; // 最大、次大、第三大
        for (int[] pr : p) {
            pr[0] = Integer.MIN_VALUE;
        }
        for (int i = m - 1; i > 1; i--) {
            update(board[i], p);
            for (int j = 0; j < 3; j++) {
                suf[i][j][0] = p[j][0];
                suf[i][j][1] = p[j][1];
            }
        }

        long ans = Long.MIN_VALUE;
        for (int[] pr : p) {
            pr[0] = Integer.MIN_VALUE; // 重置，计算 pre
        }
        for (int i = 1; i < m - 1; i++) {
            update(board[i - 1], p);
            for (int j = 0; j < n; j++) { // 第二个车
                for (int[] a : p) { // 第一个车
                    for (int[] b : suf[i + 1]) { // 第三个车
                        if (a[1] != j && b[1] != j && a[1] != b[1]) { // 没有同列的车
                            ans = Math.max(ans, (long) a[0] + board[i][j] + b[0]);
                            break;
                        }
                    }
                }
            }
        }
        return ans;
    }

    private void update(int[] row, int[][] p) {
        for (int j = 0; j < row.length; j++) {
            int x = row[j];
            if (x > p[0][0]) {
                if (p[0][1] != j) { // 如果相等，仅更新最大
                    if (p[1][1] != j) { // 如果相等，仅更新最大和次大
                        p[2] = p[1];
                    }
                    p[1] = p[0];
                }
                p[0] = new int[]{x, j};
            } else if (x > p[1][0] && j != p[0][1]) {
                if (p[1][1] != j) { // 如果相等，仅更新次大
                    p[2] = p[1];
                }
                p[1] = new int[]{x, j};
            } else if (x > p[2][0] && j != p[0][1] && j != p[1][1]) {
                p[2] = new int[]{x, j};
            }
        }
    }
}

python3 解法, 执行用时: 1156 ms, 内存消耗: 40.8 MB, 提交时间: 2024-10-13 23:40:50

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        def update(row: List[int]) -> None:
            for j, x in enumerate(row):
                if x > p[0][0]:
                    if p[0][1] != j:  # 如果相等，仅更新最大
                        if p[1][1] != j:  # 如果相等，仅更新最大和次大
                            p[2] = p[1]
                        p[1] = p[0]
                    p[0] = (x, j)
                elif x > p[1][0] and j != p[0][1]:
                    if p[1][1] != j:  # 如果相等，仅更新次大
                        p[2] = p[1]
                    p[1] = (x, j)
                elif x > p[2][0] and j != p[0][1] and j != p[1][1]:
                    p[2] = (x, j)

        m = len(board)
        suf = [None] * m
        p = [(-inf, -1)] * 3  # 最大、次大、第三大
        for i in range(m - 1, 1, -1):
            update(board[i])
            suf[i] = p[:]

        ans = -inf
        p = [(-inf, -1)] * 3  # 重置，计算 pre
        for i, row in enumerate(board[:-2]):
            update(row)
            for j2, y in enumerate(board[i + 1]):  # 第二个车
                for x, j1 in p:  # 第一个车
                    for z, j3 in suf[i + 2]:  # 第三个车
                        if j1 != j2 and j1 != j3 and j2 != j3:  # 没有同列的车
                            ans = max(ans, x + y + z)  # 注：手动 if 更快
                            break
        return ans

golang 解法, 执行用时: 268 ms, 内存消耗: 33.3 MB, 提交时间: 2024-10-13 23:39:36

func maximumValueSum(board [][]int) int64 {
	m, n := len(board), len(board[0])
	// rid 为反向边在邻接表中的下标
	type neighbor struct{ to, rid, cap, cost int }
	g := make([][]neighbor, m+n+3)
	addEdge := func(from, to, cap, cost int) {
		g[from] = append(g[from], neighbor{to, len(g[to]), cap, cost})
		g[to] = append(g[to], neighbor{from, len(g[from]) - 1, 0, -cost})
	}
	R := m + n
	C := m + n + 1
	S := m + n + 2
	for i, row := range board {
		for j, x := range row {
			addEdge(i, m+j, 1, -x)
		}
		addEdge(R, i, 1, 0)
	}
	for j := range board[0] {
		addEdge(m+j, C, 1, 0)
	}
	addEdge(S, R, 3, 0) // 把 3 改成 k 可以支持 k 个车

	// 下面是费用流模板
	dis := make([]int, len(g))
	type vi struct{ v, i int }
	fa := make([]vi, len(g))
	inQ := make([]bool, len(g))
	spfa := func() bool {
		for i := range dis {
			dis[i] = math.MaxInt
		}
		dis[S] = 0
		inQ[S] = true
		q := []int{S}
		for len(q) > 0 {
			v := q[0]
			q = q[1:]
			inQ[v] = false
			for i, e := range g[v] {
				if e.cap == 0 {
					continue
				}
				w := e.to
				newD := dis[v] + e.cost
				if newD < dis[w] {
					dis[w] = newD
					fa[w] = vi{v, i}
					if !inQ[w] {
						inQ[w] = true
						q = append(q, w)
					}
				}
			}
		}
		// 循环结束后所有 inQ[v] 都为 false，无需重置
		return dis[C] < math.MaxInt
	}

	minCost := 0
	for spfa() {
		minF := math.MaxInt
		for v := C; v != S; {
			p := fa[v]
			minF = min(minF, g[p.v][p.i].cap)
			v = p.v
		}
		for v := C; v != S; {
			p := fa[v]
			e := &g[p.v][p.i]
			e.cap -= minF
			g[v][e.rid].cap += minF
			v = p.v
		}
		minCost += dis[C] * minF
	}
	return int64(-minCost)
}