Problem:
 Score : 100 points    Problem Statement You are given a grid of N rows and M columns. The square at the i -th row and j -th column will be denoted as (i,j) .
A nonnegative integer A_{i,j} is written for each square (i,j) .  You choose some of the squares so that each row and column contains at most K chosen squares.
Under this constraint, calculate the maximum value of the sum of the integers written on the chosen squares.
Additionally, calculate a way to choose squares that acheives the maximum.      Constraints  1 \leq N \leq 50  1 \leq K \leq N  0 \leq A_{i,j} \leq 10^9  All values in Input are integer.         Input Input is given from Standard Input in the following format:  N  K  A_{1,1}  A_{1,2}  \cdots  A_{1,N}  A_{2,1}  A_{2,2}  \cdots  A_{2,N}  \vdots  A_{N,1}  A_{N,2}  \cdots  A_{N,N}       Output On the first line, print the maximum value of the sum of the integers written on the chosen squares.  On the next N lines, print a way that achieves the maximum.  Precisely, output the strings t_1,t_2,\cdots,t_N , that satisfies t_{i,j}= X if you choose (i,j) and t_{i,j}= . otherwise.  You may print any way to choose squares that maximizes the sum.        Sample Input 1 3 1
5 3 2
1 4 8
7 6 9      Sample Output 1 19
X..
..X
.X.       Sample Input 2 3 2
10 10 1
10 10 1
1 1 10      Sample Output 2 50
XX.
XX.
..X

Solution (Python):

from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        forward = [to, cap, cost, None]
        backward = forward[3] = [fr, 0, -cost, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def flow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [None]*N

        d0 = [INF]*N
        dist = [INF]*N

        while f:
            dist[:] = d0
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                r0 = dist[v] + H[v]
                for e in G[v]:
                    w, cap, cost, _ = e
                    if cap > 0 and r0 + cost - H[w] < dist[w]:
                        dist[w] = r = r0 + cost - H[w]
                        prv_v[w] = v; prv_e[w] = e
                        heappush(que, (r, w))
            if dist[t] == INF:
                return None

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, prv_e[v][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = prv_e[v]
                e[1] -= d
                e[3][1] += d
                v = prv_v[v]
        return res





from sys import stdin
input = stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]

    mcf = MinCostFlow(n*(n+2) + 2)

    source = n*(n+2)
    sink = n*(n+2) + 1

    
    
    mcf.add_edge(source, sink, n*k, 0)

    for i in range(n):
        
        mcf.add_edge(source, n*n + i, k, 0)
        
        mcf.add_edge(n*(n+1) + i, sink, k, 0)

        for j in range(n):
            
            mcf.add_edge(n*n + i, n*i + j, 1, -a[i][j])
            
            mcf.add_edge(n*i + j, n*(n+1) + j, 1, 0)

    print(-mcf.flow(source, sink, n*k))

    ans = [['.'] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if mcf.G[n*i + j][0][1]:
                ans[i][j] = 'X'

    for row in ans:
        print(''.join(row))

main()

Solution (Python):
import types

_atcoder_code = """


__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_mincostflow_code = """
from __future__ import annotations

from typing import NamedTuple, Optional, List
from heapq import heappush, heappop


class MCFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int
        cost: int

    class _Edge:
        def __init__(self, dst: int, cap: int, cost: int) -> None:
            self.dst = dst
            self.cap = cap
            self.cost = cost
            self.rev: Optional[MCFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MCFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MCFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int, cost: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MCFGraph._Edge(dst, cap, cost)
        re = MCFGraph._Edge(src, 0, -cost)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = e.rev
        return MCFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap,
            e.cost
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> (int, int):
        return self.slope(s, t, flow_limit)[-1]

    def slope(self, s: int, t: int, flow_limit: Optional[int] = None) -> List[(int, int)]:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = sum(e.cap for e in self._g[s])

        dual = [0] * self._n
        prev: List[Optional[(int, MCFGraph._Edge)]] = [None] * self._n

        def refine_dual() -> bool:
            pq = [(0, s)]
            visited = [False] * self._n
            dist: List[Optional[int]] = [None] * self._n
            dist[s] = 0
            while pq:
                dist_v, v = heappop(pq)
                if visited[v]:
                    continue
                visited[v] = True
                if v == t:
                    break
                dual_v = dual[v]
                for e in self._g[v]:
                    w = e.dst
                    if visited[w] or e.cap == 0:
                        continue
                    reduced_cost = e.cost - dual[w] + dual_v
                    new_dist = dist_v + reduced_cost
                    dist_w = dist[w]
                    if dist_w is None or new_dist < dist_w:
                        dist[w] = new_dist
                        prev[w] = v, e
                        heappush(pq, (new_dist, w))
            else:
                return False
            dist_t = dist[t]
            for v in range(self._n):
                if visited[v]:
                    dual[v] -= dist_t - dist[v]
            return True

        flow = 0
        cost = 0
        prev_cost_per_flow: Optional[int] = None
        result = [(flow, cost)]
        while flow < flow_limit:
            if not refine_dual():
                break
            f = flow_limit - flow
            v = t
            while prev[v] is not None:
                u, e = prev[v]
                f = min(f, e.cap)
                v = u
            v = t
            while prev[v] is not None:
                u, e = prev[v]
                e.cap -= f
                e.rev.cap += f
                v = u
            c = -dual[s]
            flow += f
            cost += f * c
            if c == prev_cost_per_flow:
                result.pop()
            result.append((flow, cost))
            prev_cost_per_flow = c
        return result
"""

atcoder.mincostflow = types.ModuleType('atcoder.mincostflow')
exec(_atcoder_mincostflow_code, atcoder.mincostflow.__dict__)
MCFGraph = atcoder.mincostflow.MCFGraph



import sys




def main() -> None:
    n, k = map(int, sys.stdin.readline().split())
    s = n * 2
    t = s + 1
    g = MCFGraph(t + 1)
    grid = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    big = 10 ** 9
    edges = list([] for _ in range(n))
    for i in range(n):
        g.add_edge(s, i, k, 0)
        g.add_edge(i + n, t, k, 0)
        for j in range(n):
            edges[i].append(g.add_edge(i, j + n, 1, big - grid[i][j]))
    g.add_edge(s, t, n * k, big)

    cost = g.flow(s, t, n * k)[1]
    print(big * n * k - cost)

    result = list(['.'] * n for _ in range(n))
    for i in range(n):
        for j in range(n):
            if g.get_edge(edges[i][j]).flow > 0:
                result[i][j] = 'X'

    for s in result:
        print("".join(s))


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop, heappush


NUMERIC_LIMITS = (1 << 63) - 1


class McfGraph:
  def __init__(self, n):
    self._n = n
    self.g = [[] for _ in range(n)]
    self.pos = []

  def add_edge(self, frm, to, cap, cost):
    m = len(self.pos)
    self.pos.append([frm, len(self.g[frm])])
    self.g[frm].append(self._edge(to, len(self.g[to]), cap, cost))
    self.g[to].append(self._edge(frm, len(self.g[frm]) - 1, 0, -cost))
    return m

  class edge:
    __slots__ = "frm", "to", "cap", "flow", "cost"

    def __init__(self, frm, to, cap, flow, cost):
      self.frm, self.to = frm, to
      self.cap, self.flow, self.cost = cap, flow, cost

  def get_edge(self, i):
    _e = self.g[self.pos[i][0]][self.pos[i][1]]
    _re = self.g[_e.to][_e.rev]
    return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)

  def edges(self):
    for i in range(len(self.pos)):
      yield self.get_edge(i)

  def flow(self, s, t, flow_limit=NUMERIC_LIMITS):
    return self.slope(s, t, flow_limit)[-1]

  def dual_ref(self, s, t):
    dist = [NUMERIC_LIMITS] * self._n
    self.pv = [-1] * self._n
    self.pe = [-1] * self._n
    vis = [False] * self._n
    que = []
    dist[s] = 0
    heappush(que, (0, s))
    while que:
      _, v = heappop(que)
      if vis[v]:
        continue
      vis[v] = True
      if v == t:
        break
      for i in range(len(self.g[v])):
        e = self.g[v][i]
        if vis[e.to] or not e.cap:
          continue
        cost = e.cost - self.dual[e.to] + self.dual[v]
        if dist[e.to] - dist[v] > cost:
          dist[e.to] = dist[v] + cost
          self.pv[e.to] = v
          self.pe[e.to] = i
          heappush(que, (dist[e.to], e.to))
    if not vis[t]:
      return False
    for v in range(self._n):
      if not vis[v]:
        continue
      self.dual[v] -= dist[t] - dist[v]
    return True

  def slope(self, s, t, flow_limit=NUMERIC_LIMITS):
    self.dual = [0] * self._n

    flow = 0
    cost, prev_cost = 0, -1
    result = [(flow, cost)]
    while flow < flow_limit:
      if not self.dual_ref(s, t):
        break
      c = flow_limit - flow
      v = t
      while v != s:
        c = min(c, self.g[self.pv[v]][self.pe[v]].cap)
        v = self.pv[v]
      v = t
      while v != s:
        e = self.g[self.pv[v]][self.pe[v]]
        e.cap -= c
        self.g[v][e.rev].cap += c
        v = self.pv[v]
      d = -self.dual[s]
      flow += c
      cost += c * d
      if prev_cost == d:
        result.pop()
      result.append((flow, cost))
      prev_cost = cost
    return result

  class _edge:
    __slots__ = "to", "rev", "cap", "cost"

    def __init__(self, to, rev, cap, cost):
      self.to, self.rev, self.cap, self.cost = to, rev, cap, cost


def atcoder_practice2_e():
    import sys
    input = sys.stdin.buffer.readline

    N, K = list(map(int, input().split()))
    A = [tuple(map(int, input().split())) for _ in range(N)]
    BIG = 10 ** 9

    g = McfGraph(2 * N + 2)
    s = 2 * N
    t = 2 * N + 1

    g.add_edge(s, t, N * K, BIG)

    for i in range(N):
        g.add_edge(s, i, K, 0)
        g.add_edge(N + i, t, K, 0)
    for i in range(N):
        for j in range(N):
            g.add_edge(i, N + j, 1, BIG - A[i][j])

    result = g.flow(s, t, N * K)
    print(N * K * BIG - result[1])

    grid = [["."] * N for _ in range(N)]
    edges = g.edges()
    for e in edges:
        if e.frm == s or e.to == t or e.flow == 0:
            continue
        grid[e.frm][e.to - N] = "X"

    for g in grid:
        print("".join(g))


if __name__ == "__main__":
    atcoder_practice2_e()