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



Sample input:
3 1
5 3 2
1 4 8
7 6 9


Sample output:
19
X..
..X
.X.

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class MinCostFlow:
    """ 最小費用流(ベルマンフォード版、負コストに対応可)：O(F*E*V) """

    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]
        self.pos = []
    
    def copy(self):
        res = MinCostFlow(self.N)
        res.G = [[a[:] for a in b] for b in self.G]
        res.pos = [a[:] for a in self.pos]
        return res

    def add_edge(self, fr, to, cap, cost):
        self.pos.append((fr, len(self.G[fr])))
        self.G[fr].append([to, cap, cost, len(self.G[to])])
        self.G[to].append([fr, 0, -cost, len(self.G[fr])-1])

    def flow(self, s, t, f):

        N = self.N; G = self.G
        INF = MinCostFlow.INF

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

        while f:
            dist = [INF] * N
            dist[s] = 0
            update = True

            while update:
                update = False
                for v in range(N):
                    if dist[v] == INF:
                        continue
                    for i, (to, cap, cost, _) in enumerate(G[v]):
                        if cap > 0 and dist[to] > dist[v] + cost:
                            dist[to] = dist[v] + cost
                            prv_v[to] = v; prv_e[to] = i
                            update = True
            if dist[t] == INF:
                return INF

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

    def get_edge(self, i):
        e = self.G[self.pos[i][0]][self.pos[i][1]]
        re = self.G[e[0]][e[3]]
        # from, to, cap, flow, cost
        return (self.pos[i][0], e[0], e[1]+re[1], re[1], e[2])

    def get_edges(self):
        M = len(self.pos)
        res = []
        for i in range(M):
            res.append(self.get_edge(i))
        return res

def trisearch_min(lo, hi, func):
    """ 三分探索 """

    while lo+2 < hi:
        m1 = (lo*2+hi) // 3
        m2 = (lo+hi*2) // 3
        res1 = func(m1)
        res2 = func(m2)
        if res1 <= res2:
            hi = m2
        else:
            lo = m1
    return m1, m2

N, K = MAP()
grid = [[] for i in range(N)]
for i in range(N):
    grid[i] = LIST()

mcf = MinCostFlow(N*2+2)
s = N*2
t = N*2 + 1
for i in range(N):
    mcf.add_edge(s, i, K, 0)
    mcf.add_edge(N+i, t, K, 0)
    for j in range(N):
        mcf.add_edge(i, N+j, 1, -grid[i][j])

def check(x):
    global mcf

    tmp = mcf.copy()
    res = mcf.flow(s, t, x)
    mcf = tmp
    return res

m1, m2 = trisearch_min(-1, N*N+1, check)
x = m1 if check(m1) <= check(m2) else m2

mx = -mcf.flow(s, t, x)
ans = [['.' for j in range(N)] for i in range(N)]
edges = mcf.get_edges()
for fr, to, cap, f, c in edges:
    if fr != s and to != t and f:
        h = fr
        w = to - N
        ans[h][w] = 'X'
print(mx)
for i in range(N):
    print(''.join(ans[i]))

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class MinCostFlow:
    """ 最小費用流(ベルマンフォード版、負コストに対応可)：O(F*E*V) """

    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]
        self.pos = []
    
    def copy(self):
        res = MinCostFlow(self.N)
        res.G = [[a[:] for a in b] for b in self.G]
        res.pos = [a[:] for a in self.pos]
        return res

    def add_edge(self, fr, to, cap, cost):
        self.pos.append((fr, len(self.G[fr])))
        self.G[fr].append([to, cap, cost, len(self.G[to])])
        self.G[to].append([fr, 0, -cost, len(self.G[fr])-1])

    def flow(self, s, t, f):

        N = self.N; G = self.G
        INF = MinCostFlow.INF

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

        while f:
            dist = [INF] * N
            dist[s] = 0
            update = True

            while update:
                update = False
                for v in range(N):
                    if dist[v] == INF:
                        continue
                    for i, (to, cap, cost, _) in enumerate(G[v]):
                        if cap > 0 and dist[to] > dist[v] + cost:
                            dist[to] = dist[v] + cost
                            prv_v[to] = v; prv_e[to] = i
                            update = True
            if dist[t] == INF:
                return INF

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

    def get_edge(self, i):
        e = self.G[self.pos[i][0]][self.pos[i][1]]
        re = self.G[e[0]][e[3]]
        # from, to, cap, flow, cost
        return (self.pos[i][0], e[0], e[1]+re[1], re[1], e[2])

    def get_edges(self):
        M = len(self.pos)
        res = []
        for i in range(M):
            res.append(self.get_edge(i))
        return res

N, K = MAP()
grid = [[] for i in range(N)]
for i in range(N):
    grid[i] = LIST()

mcf = MinCostFlow(N*2+2)
s = N*2
t = N*2 + 1
for i in range(N):
    mcf.add_edge(s, i, K, 0)
    mcf.add_edge(N+i, t, K, 0)
    for j in range(N):
        mcf.add_edge(i, N+j, 1, -grid[i][j])

mx = 0
for x in range(1, N*N+1):
    tmp = mcf.copy()
    res = -mcf.flow(s, t, x)
    if res > mx:
        mx = res
        ans = [['.' for j in range(N)] for i in range(N)]
        edges = mcf.get_edges()
        for fr, to, cap, f, c in edges:
            if fr != s and to != t and f:
                h = fr
                w = to - N
                ans[h][w] = 'X'
    else:
        break
    mcf = tmp
print(mx)
for i in range(N):
    print(''.join(ans[i]))

Submission status: Time Limit Exceeded

Solution code:
#-------最強ライブラリMinCostFlow(Python)------
#速度確認

import heapq
# numeric_limitsわかんね
NUMERIC_LIMITS = 10 ** 18

class mcf_graph:
  pos = []
  def __init__(s):
    None
  def __init__ (s, n):
    s._n = n
    s.g = [[] for _ in range(n)]

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

  class edge:
    def __init__(s, frm, to, cap, flow, cost):
      s.frm, s.to = frm, to
      s.cap, s.flow, s.cost = cap, flow, cost

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

  def edges(s):
    return [s.get_edge(i) for i in range(len(s.pos))]
   
  def flow(self, s, t):
    return self.flow(s, t, NUMERIC_LIMITS)

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

  def slope(self, s, t):
    return self.slope(s, t, NUMERIC_LIMITS)

  def slope(self, s, t, flow_limit):
    #priority_queueの代わり
    push = heapq.heappush
    pop = heapq.heappop
    dual, dist = [0] * self._n, [0] * self._n
    pv, pe = [0] * self._n, [0] * self._n
    vis = [False] * self._n

    def dual_ref():
      for i in range(self._n):
        dist[i] = NUMERIC_LIMITS
        pv[i] = -1
        pe[i] = -1
        vis[i] = False
      class Q:
        def __init__(s, key, to):
          s.key = key
          s.to = to
        def __lt__(s, r):
          return s.key < r.key
      que = []
      dist[s] = 0
      push(que, Q(0, s))
      while len(que):
        v = pop(que).to
        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 - dual[e.to] + dual[v]
          if dist[e.to] - dist[v] > cost:
            dist[e.to] = dist[v] + cost
            pv[e.to] = v
            pe[e.to] = i
            push(que, Q(dist[e.to], e.to))
      if not vis[t]: return False
      for v in range(self._n):
        if not vis[v]: continue
        dual[v] -= dist[t] - dist[v]
      return True
    
    flow = 0
    cost, prev_cost = 0, -1
    result = []
    result.append([flow, cost])
    while flow < flow_limit:
      if not dual_ref(): break
      c = flow_limit - flow
      v = t
      while v != s:
        c = min(c, self.g[pv[v]][pe[v]].cap)
        v = pv[v]
      v = t
      while v != s:
        e = self.g[pv[v]][pe[v]]
        e.cap -= c
        self.g[v][e.rev].cap += c
        v = pv[v]
      d = -dual[s]
      flow += c
      cost += c * d
      if prev_cost == d:
        result.pop()
      result.append([flow, cost])
      prev_cost = cost
    return result

  class _edge:
    def __init__(s, to, rev, cap, cost):
      s.to, s.rev = to, rev
      s.cap, s.cost = cap, cost

#-------最強ライブラリここまで------

def main():
  import sys
  input = sys.stdin.readline

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

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

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

  #   k,0|1,A[i][j]|k,0
  #      列0 ー 行0
  #   ／　　 ×     ＼
  # s ー 列1 米 行1 ー t
  #   ＼  　 ×     ／
  #      列i ー 行j
  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))

main()

Submission status: Time Limit Exceeded

Solution code:
#-------最強ライブラリMinCostFlow(Python)------
#速度確認

import heapq
# numeric_limitsわかんね
NUMERIC_LIMITS = 10 ** 18

class mcf_graph:
  pos = []
  def __init__(s):
    None
  def __init__ (s, n):
    s._n = n
    s.g = [[] for _ in range(n)]

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

  class edge:
    def __init__(s, frm, to, cap, flow, cost):
      s.frm, s.to = frm, to
      s.cap, s.flow, s.cost = cap, flow, cost

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

  def edges(s):
    return [s.get_edge(i) for i in range(len(s.pos))]
   
  def flow(self, s, t):
    return self.flow(s, t, NUMERIC_LIMITS)

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

  def slope(self, s, t):
    return self.slope(s, t, NUMERIC_LIMITS)

  def slope(self, s, t, flow_limit):
    #priority_queueの代わり
    push = heapq.heappush
    pop = heapq.heappop
    dual, dist = [0] * self._n, [0] * self._n
    pv, pe = [0] * self._n, [0] * self._n
    vis = [False] * self._n

    def dual_ref():
      for i in range(self._n):
        dist[i] = NUMERIC_LIMITS
        pv[i] = -1
        pe[i] = -1
        vis[i] = False
      class Q:
        def __init__(s, key, to):
          s.key = key
          s.to = to
        def __lt__(s, r):
          return s.key < r.key
      que = []
      dist[s] = 0
      push(que, Q(0, s))
      while len(que):
        v = pop(que).to
        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 - dual[e.to] + dual[v]
          if dist[e.to] - dist[v] > cost:
            dist[e.to] = dist[v] + cost
            pv[e.to] = v
            pe[e.to] = i
            push(que, Q(dist[e.to], e.to))
      if not vis[t]: return False
      for v in range(self._n):
        if not vis[v]: continue
        dual[v] -= dist[t] - dist[v]
      return True
    
    flow = 0
    cost, prev_cost = 0, -1
    result = []
    result.append([flow, cost])
    while flow < flow_limit:
      if not dual_ref(): break
      c = flow_limit - flow
      v = t
      while v != s:
        c = min(c, self.g[pv[v]][pe[v]].cap)
        v = pv[v]
      v = t
      while v != s:
        e = self.g[pv[v]][pe[v]]
        e.cap -= c
        self.g[v][e.rev].cap += c
        v = pv[v]
      d = -dual[s]
      flow += c
      cost += c * d
      if prev_cost == d:
        result.pop()
      result.append([flow, cost])
      prev_cost = cost
    return result

  class _edge:
    def __init__(s, to, rev, cap, cost):
      s.to, s.rev = to, rev
      s.cap, s.cost = cap, cost

#-------最強ライブラリここまで------

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

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

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

  #   k,0|1,A[i][j]|k,0
  #      列0 ー 行0
  #   ／　　 ×     ＼
  # s ー 列1 米 行1 ー t
  #   ＼  　 ×     ／
  #      列i ー 行j
  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))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
import networkx as nx
ans = (-float("inf"), None)
for f in range(1,n*k+1):
    g = nx.DiGraph()
    for i in range(2*n):
        g.add_node(i)
    g.add_node(2*n, demand=-f)
    g.add_node(2*n+1, demand=f)
    for i in range(n):
        g.add_edge(2*n, i, capacity=k, weight=0)
        g.add_edge(i+n, 2*n+1, capacity=k, weight=0)

    for i in range(n):
        for j in range(n):
            g.add_edge(i, j+n, capacity=1, weight=-a[i][j])
    val, d = nx.network_simplex(g)
    vals = [["."]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if d[i][j+n]==1:
                vals[i][j] = "X"
    if -val>ans[0]:
        ans = (-val, vals)
print(ans[0])
print("\n".join("".join(ans[1][i]) for i in range(n)))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
# import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)
def IF(c, t, f): return t if c else f


class Edge():
    def __init__(self,t,f,r,ca,co):
        self.to = t
        self.fron = f
        self.rev = r
        self.cap = ca
        self.cost = co

class MinCostFlow():
    size = 0
    graph = []

    def __init__(self, s):
        self.size = s
        self.graph = [[] for _ in range(s)]

    def add_edge(self, f, t, ca, co):
        self.graph[f].append(Edge(t, f, len(self.graph[t]), ca, co))
        self.graph[t].append(Edge(f, t, len(self.graph[f])-1, 0, -co))

    def min_path(self, s, t):
        dist = [inf] * self.size
        route = [None] * self.size
        que = collections.deque()
        inq = [False] * self.size
        dist[s] = 0
        que.append(s)
        inq[s] = True
        while que:
            u = que.popleft()
            inq[u] = False
            for e in self.graph[u]:
                if e.cap == 0:
                    continue
                v = e.to
                if dist[v] > dist[u] + e.cost:
                    dist[v] = dist[u] + e.cost
                    route[v] = e
                    if not inq[v]:
                        que.append(v)
                        inq[v] = True

        if dist[t] == inf:
            return inf, 0

        # 途中終了する場合
        if dist[t] > 0:
            return dist[t], -1

        flow = inf
        v = t
        while v != s:
            e = route[v]
            if flow > e.cap:
                flow = e.cap
            v = e.fron

        c = 0
        v = t
        while v != s:
            e = route[v]
            e.cap -= flow
            self.graph[e.to][e.rev].cap += flow
            c += e.cost * flow
            v = e.fron

        return dist[t], flow

    def calc_min_cost_flow(self, s, t, flow):
        total_cost = 0
        while flow > 0:
            c,f = self.min_path(s, t)
            if f == 0:
                return inf
            if f < 0:
                return total_cost
            f = min(flow, f)
            total_cost += c * f
            flow -= f

        return total_cost


def main():
    n,k = LI()
    aa = [LI() for _ in range(n)]

    ri = [n*n+i for i in range(n)]
    ci = [n*n+n+i for i in range(n)]
    s = n*n+n*2
    t = n*n+n*2+1
    mcf = MinCostFlow(n*n+n*2+2)
    for i in range(n):
        mcf.add_edge(s, ri[i], k, 0)
        mcf.add_edge(ci[i], t, k, 0)

    for r in range(n):
        for c in range(n):
            rc = r*n+c
            mcf.add_edge(ri[r], rc, 1, -aa[r][c])
            mcf.add_edge(rc, ci[c], 1, 0)

    res = -mcf.calc_min_cost_flow(s,t,n*k)
    ra = [['.']*n for _ in range(n)]
    for r in range(n):
        for c in range(n):
            rc = r*n+c
            for gr in  mcf.graph[rc]:
                if gr.to == ci[c] and gr.cap == 0:
                    ra[r][c] = 'X'

    return f"{res}\n" + JAA(ra, "\n", "")


print(main())

Submission status: Accepted

Solution code:
# Reference: https://tjkendev.github.io/procon-library/python/min_cost_flow/primal-dual.html
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

###

# source >>> 1~n rows >>> (1,1)~(n,n) squares >>> 1~n columns >>> sink

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

    # add edges
    #source >>> sink
    mcf.add_edge(source, sink, n*k, 0)

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

        for j in range(n):
            # rows >>> squares
            mcf.add_edge(n*n + i, n*i + j, 1, -a[i][j])
            # squares >>> columns
            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()

Submission status: Accepted

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__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

# https://atcoder.jp/contests/practice2/tasks/practice2_e

import sys

# from atcoder.mincostflow import MCFGraph


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()