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 heapq
# numeric_limitsわかんね
NUMERIC_LIMITS = 10 ** 18

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

  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:
    __slots__ = "frm", "to", "cap", "flow", "cost"
    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):
    _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):
    for i in range(len(s.pos)):
      yield s.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):
    #priority_queueの代わり
    push = heapq.heappush
    pop = heapq.heappop

    dist = [NUMERIC_LIMITS] * self._n
    self.pv = [-1] * self._n
    self.pe = [-1] * self._n
    vis = [False] * self._n
    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 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 - 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
          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
      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__(s, to, rev, cap, cost):
      s.to, s.rev = to, rev
      s.cap, s.cost = cap, cost

N, K = list(map(int, input().split()))
A = [tuple(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))

Submission status: Time Limit Exceeded

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

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

  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:
    __slots__ = "frm", "to", "cap", "flow", "cost"
    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):
    for i in range(len(s.pos)):
      yield s.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):
    #priority_queueの代わり
    push = heapq.heappush
    pop = heapq.heappop

    dist = [NUMERIC_LIMITS] * self._n
    self.pv = [-1] * self._n
    self.pe = [-1] * self._n
    vis = [False] * self._n
    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 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 - 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
          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
      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__(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 heapq
# numeric_limitsわかんね
NUMERIC_LIMITS = 10 ** 18

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

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

  class edge(object):
    __slots__ = "frm", "to", "cap", "flow", "cost"
    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[0]][_e[1]]
    return s.edge(s.pos[i][0], _e[0], _e[2] + _re[2], _re[2], _e[3])

  def edges(s):
    return [s.get_edge(i) for i in range(len(s.pos))]

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

  def slope(self, s, t, flow_limit = NUMERIC_LIMITS):
    #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[0]] or not e[2]: continue
          cost = e[3] - dual[e[0]] + dual[v]
          if dist[e[0]] - dist[v] > cost:
            dist[e[0]] = dist[v] + cost
            pv[e[0]] = v
            pe[e[0]] = i
            push(que, Q(dist[e[0]], e[0]))
      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]][2])
        v = pv[v]
      v = t
      while v != s:
        e = self.g[pv[v]][pe[v]]
        e[2] -= c
        self.g[v][e[1]][2] += 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

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

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 heapq
# numeric_limitsわかんね
NUMERIC_LIMITS = 10 ** 18

class mcf_graph:
  pos = []
  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([to, len(s.g[to]), cap, cost])
    s.g[to].append([frm, len(s.g[frm]) - 1, 0, -cost])
    return m

  class edge(object):
    __slots__ = "frm", "to", "cap", "flow", "cost"
    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[0]][_e[1]]
    return s.edge(s.pos[i][0], _e[0], _e[2] + _re[2], _re[2], _e[3])

  def edges(s):
    return [s.get_edge(i) for i in range(len(s.pos))]

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

  def slope(self, s, t, flow_limit = NUMERIC_LIMITS):
    #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[0]] or not e[2]: continue
          cost = e[3] - dual[e[0]] + dual[v]
          if dist[e[0]] - dist[v] > cost:
            dist[e[0]] = dist[v] + cost
            pv[e[0]] = v
            pe[e[0]] = i
            push(que, Q(dist[e[0]], e[0]))
      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]][2])
        v = pv[v]
      v = t
      while v != s:
        e = self.g[pv[v]][pe[v]]
        e[2] -= c
        self.g[v][e[1]][2] += 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

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

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 heapq
# numeric_limitsわかんね
NUMERIC_LIMITS = 10 ** 18

class mcf_graph:
  pos = []
  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([to, len(s.g[to]), cap, cost])
    s.g[to].append([frm, len(s.g[frm]) - 1, 0, -cost])
    return m

  class edge:
    __slots__ = "frm", "to", "cap", "flow", "cost"
    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[0]][_e[1]]
    return s.edge(s.pos[i][0], _e[0], _e[2] + _re[2], _re[2], _e[3])

  def edges(s):
    return [s.get_edge(i) for i in range(len(s.pos))]

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

  def slope(self, s, t, flow_limit = NUMERIC_LIMITS):
    #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[0]] or not e[2]: continue
          cost = e[3] - dual[e[0]] + dual[v]
          if dist[e[0]] - dist[v] > cost:
            dist[e[0]] = dist[v] + cost
            pv[e[0]] = v
            pe[e[0]] = i
            push(que, Q(dist[e[0]], e[0]))
      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]][2])
        v = pv[v]
      v = t
      while v != s:
        e = self.g[pv[v]][pe[v]]
        e[2] -= c
        self.g[v][e[1]][2] += 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

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

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 heapq
# numeric_limitsわかんね
NUMERIC_LIMITS = 10 ** 18

class mcf_graph:
  pos = []
  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:
    __slots__ = "frm", "to", "cap", "flow", "cost"
    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, flow_limit = NUMERIC_LIMITS):
    return self.slope(s, t, flow_limit)[-1]

  def slope(self, s, t, flow_limit = NUMERIC_LIMITS):
    #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:
    __slots__ = "to", "rev", "cap", "cost"
    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 heapq
# numeric_limitsわかんね
NUMERIC_LIMITS = 10 ** 18

class mcf_graph:
  pos = []
  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, flow_limit = NUMERIC_LIMITS):
    return self.slope(s, t, flow_limit)[-1]

  def slope(self, s, t, flow_limit = NUMERIC_LIMITS):
    #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

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**18
MOD = 10**9 + 7
EPS = 10**-10

class MinCostFlow:
    """ 最小費用流(ダイクストラ版2)：O(F*V^2) """

    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
        H = [0] * N
        prv_v = [0] * N
        prv_e = [0] * N

        while f:
            dist = [INF] * N
            dist[s] = 0
            used = [False] * N

            while True:
                v = -1
                for u in range(N):
                    if not used[u] and (v == -1 or dist[u] < dist[v]):
                        v = u
                if v == -1:
                    break
                used[v] = True
                for i, (to, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[to] > dist[v] + cost + H[v] - H[to]:
                        dist[to] = dist[v] + cost + H[v] - H[to]
                        prv_v[to] = v; prv_e[to] = i
            if dist[t] == INF:
                return INF

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

            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 * H[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()

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

def check(x):
    global mcf

    tmp = mcf.copy()
    res = mcf.flow(s, t, x)
    if res != INF:
        res -= offset * x * 3
    mcf = tmp
    return res

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

mn = mcf.flow(s, t, x)
mn -= offset * x * 3
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(-mn)
for i in range(N):
    print(''.join(ans[i]))