2025-04-10：选择矩阵中单元格的最大得分。用go语言，给你一个由正整数构成的二维矩阵 grid。 你的任务是从这个矩阵中

package main

import (
    "fmt"
    "math"
    "math/bits"
)

func maxScore(grid [][]int)int {
    pos := map[int]int{}
    for i, row := range grid {
        for _, x := range row {
            // 保存所有包含 x 的行号（压缩成二进制数）
            pos[x] |= 1 << i
        }
    }

    // 建图
    k := len(pos)
    m := len(grid)
    // rid 为反向边在邻接表中的下标
    type neighbor struct{ to, rid, cap, cost int }
    g := make([][]neighbor, k+m+2)
    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})
    }
    S := k + m
    T := k + m + 1
    i := 0
    for x, posMask := range pos {
        for t := uint(posMask); t > 0; t &= t - 1 {
            j := bits.TrailingZeros(t)
            addEdge(i, k+j, 1, 0)
        }
        addEdge(S, i, 1, -x)
        i++
    }
    for j := range grid {
        addEdge(k+j, T, 1, 0)
    }

    // 下面是费用流模板
    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}
        forlen(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[T] < math.MaxInt
    }

    minCost := 0
    for spfa() {
        minF := math.MaxInt
        for v := T; v != S; {
            p := fa[v]
            minF = min(minF, g[p.v][p.i].cap)
            v = p.v
        }
        for v := T; 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[T] * minF
    }
    return -minCost
}

func main() {
    grid := [][]int{{1, 2, 3}, {4, 3, 2}, {1, 1, 1}}
    results := maxScore(grid)
    fmt.Println(results)
}

# -*-coding:utf-8-*-

from collections import defaultdict
import math
from queue import SimpleQueue

defmaxScore(grid):
    pos = defaultdict(int)

    # 保存所有包含 x 的行号（压缩成二进制数）
    for i, row inenumerate(grid):
        for x in row:
            pos[x] |= 1 << i

    # 建图
    k = len(pos)
    m = len(grid)
    S = k + m
    T = k + m + 1
    
    g = [[] for _ inrange(k + m + 2)]
    
    defadd_edge(from_node, to_node, cap, cost):
        g[from_node].append([to_node, len(g[to_node]), cap, cost])
        g[to_node].append([from_node, len(g[from_node]) - 1, 0, -cost])

    i = 0
    for x, pos_mask in pos.items():
        for j inrange(m):
            if (pos_mask >> j) & 1:
                add_edge(i, k + j, 1, 0)
        add_edge(S, i, 1, -x)
        i += 1
    
    for j inrange(m):
        add_edge(k + j, T, 1, 0)

    # 费用流模板
    dis = [math.inf] * len(g)
    fa = [(-1, -1)] * len(g)
    in_q = [False] * len(g)

    defspfa():
        nonlocal dis, fa, in_q
        for i inrange(len(dis)):
            dis[i] = math.inf
        dis[S] = 0
        in_q[S] = True
        q = SimpleQueue()
        q.put(S)

        whilenot q.empty():
            v = q.get()
            in_q[v] = False
            for i, e inenumerate(g[v]):
                if e[2] == 0:  # cap
                    continue
                w = e[0]  # to
                new_d = dis[v] + e[3]  # cost
                if new_d < dis[w]:
                    dis[w] = new_d
                    fa[w] = (v, i)
                    ifnot in_q[w]:
                        in_q[w] = True
                        q.put(w)

        return dis[T] < math.inf

    min_cost = 0
    while spfa():
        min_f = math.inf
        v = T
        while v != S:
            p = fa[v]
            min_f = min(min_f, g[p[0]][p[1]][2])  # cap
            v = p[0]
        
        v = T
        while v != S:
            p = fa[v]
            g[p[0]][p[1]][2] -= min_f  # cap
            g[v][g[p[0]][p[1]][1]][2] += min_f  # rid cap
            v = p[0]
        
        min_cost += dis[T] * min_f

    return -min_cost

if __name__ == "__main__":
    grid = [[1, 2, 3], [4, 3, 2], [1, 1, 1]]
    result = maxScore(grid)
    print(result)