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: Accepted

Solution code:
import heapq


class MCF_graph(object):
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]  # to, rev, cap, cost
        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([to, len(self.g[to]), cap, cost])
        self.g[to].append([frm, len(self.g[frm]) - 1, 0, -cost])
        return m

    def __get_edge(self, i):
        e_to, e_rev, e_cap, e_cost = self.g[self.pos[i][0]][self.pos[i][1]]
        re_to, _, re_cap, _ = self.g[e_to][e_rev]
        # from, to, cap, flow, cost
        return (re_to, e_to, e_cap + re_cap, re_cap, e_cost)

    def edges(self):
        m = len(self.pos)
        for i in range(m):
            yield self.__get_edge(i)

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

    def slope(self, s, t, flow_limit=10**18):
        dual = [0] * self.n
        flow = 0
        cost = 0
        prev_cost = -1
        result = [(0, 0)]  # cap, cost
        while flow < flow_limit:
            # call dual_ref()
            dist = [10**18] * self.n
            pv = [-1] * self.n
            pe = [-1] * self.n
            vis = [False] * self.n
            dist[s] = 0
            que = [(0, s)]
            while que:
                _, v = heapq.heappop(que)
                if vis[v]:
                    continue
                vis[v] = True
                if v == t:
                    break
                for i, (e_to, _, e_cap, e_cost) in enumerate(self.g[v]):
                    if vis[e_to] or (not e_cap):
                        continue
                    tmp_cost = e_cost - dual[e_to] + dual[v]
                    if dist[e_to] > dist[v] + tmp_cost:
                        dist[e_to] = dist[v] + tmp_cost
                        pv[e_to] = v
                        pe[e_to] = i
                        heapq.heappush(que, (dist[e_to], e_to))
            if not vis[t]:
                break
            for v, visited in enumerate(vis):
                if not visited:
                    continue
                dual[v] -= dist[t] - dist[v]
            # end dual_ref()

            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:
                i, j = pv[v], pe[v]
                self.g[i][j][2] -= c
                self.g[v][self.g[i][j][1]][2] += c
                v = i
            d = -dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                result.pop()
            result.append((flow, cost))
            prev_cost = cost
        return result


if __name__ == "__main__":
    import sys
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(10 ** 7)
    inf = 10**18

    N, K = map(int, input().split())
    g = MCF_graph(2 * N + 2)
    source = 2 * N
    sink = 2 * N + 1

    g.add_edge(source, sink, N * K, inf)
    for i in range(N):
        g.add_edge(source, i, K, 0)
        g.add_edge(N + i, sink, K, 0)

    A = list(list(map(int, input().split())) for _ in range(N))
    for i, ai in enumerate(A):
        for j, a in enumerate(ai):
            g.add_edge(i, N + j, 1, inf - a)

    res_flow, res_cost = g.flow(source, sink, N * K)
    print(N * K * inf - res_cost)

    res = [["."] * N for _ in range(N)]
    for frm, to, cap, flow, cost in g.edges():
        if frm == source or to == sink or (not flow):
            continue
        res[frm][to - N] = "X"

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

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []
        self.pv = []
        self.pe = []
        self.dual = []

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

    def get_edge(self, idx):
        to, rev, cap, cost = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap, rev_cost = self.graph[to][rev]
        return self.pos[idx][0], to, cap + rev_cap, rev_cap, cost

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

    def dual_ref(self, s, t):
        dist = [2 ** 63 - 1] * self.n
        dist[s] = 0
        vis = [0] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        queue = []
        heappush(queue, (0, s))
        while queue:
            k, v = heappop(queue)
            if vis[v]:
                continue
            vis[v] = True
            if v == t:
                break
            for i in range(len(self.graph[v])):
                to, rev, cap, cost = self.graph[v][i]
                if vis[to] or cap == 0:
                    continue
                cost += self.dual[v] - self.dual[to]
                if dist[to] - dist[v] > cost:
                    dist[to] = dist[v] + cost
                    self.pv[to] = v
                    self.pe[to] = i
                    heappush(queue, (dist[to], 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 flow(self, s, t):
        return self.flow_with_limit(s, t, 2 ** 63 - 1)

    def flow_with_limit(self, s, t, limit):
        return self.slope_with_limit(s, t, limit)[-1]

    def slope(self, s, t):
        return self.slope_with_limit(s, t, 2 ** 63 - 1)

    def slope_with_limit(self, s, t, limit):
        flow = 0
        cost = 0
        prev_cost = -1
        res = [(flow, cost)]
        self.dual = [0] * self.n
        while flow < limit:
            if not self.dual_ref(s, t):
                break
            c = limit - flow
            v = t
            while v != s:
                c = min(c, self.graph[self.pv[v]][self.pe[v]][2])
                v = self.pv[v]
            v = t
            while v != s:
                to, rev, cap, _ = self.graph[self.pv[v]][self.pe[v]]
                self.graph[self.pv[v]][self.pe[v]][2] -= c
                self.graph[v][rev][2] += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                res.pop()
            res.append((flow, cost))
            prev_cost = cost
        return res


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

mcf = MinCostFlow(2 * N + 2)
start = 2 * N
end = 2 * N + 1

MAX = 10 ** 9

mcf.add_edge(start, end, N * K, MAX)

for i in range(N):
    mcf.add_edge(start, i, K, 0)
    mcf.add_edge(N + i, end, K, 0)

    for j in range(N):
        mcf.add_edge(i, N + j, 1, MAX - A[i][j])

print(N * K * MAX - mcf.flow_with_limit(start, end, N * K)[1])

for fr, to, cap, flow, cost in mcf.edges():
    if fr == start or to == end:
        continue
    A[fr][to-N] = 'X' if flow == 1 else '.'

for r in A:
    print(''.join(r))

Submission status: Accepted

Solution code:
import networkx as nx

N,K=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(N)]
maxA = max([max(A[i]) for i in range(N)])

G = nx.DiGraph()
G.add_node('source',demand=-K*N)
G.add_node('sink',demand=K*N)
G.add_edge('source','sink',weight=maxA, capacity=K*N)
for i in range(N):
  for j in range(N):
    G.add_edge(i,N+j,weight=maxA-A[i][j],capacity=1)
    
for i in range(N):
  G.add_edge('source',i,weight=0,capacity=K)
  G.add_edge(N+i,'sink',weight=0,capacity=K)
  
flowCost,flowDict = nx.network_simplex(G)
ans=[['.']*N for _ in range(N)]
for i in flowDict.keys():
  if i in ('source','sink'):continue
  for j in flowDict[i].keys():
    if j in ('source','sink'):continue
    if flowDict[i][j]:
      ans[i][j-N] = 'X'

print(maxA*K*N-flowCost)
for i in range(N):
  print(''.join(ans[i]))

Submission status: Accepted

Solution code:
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

N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

G = MinCostFlow(2*N+2)
G.add_edge(0,2*N+1,10**18,10**9)

for i in range(N):
    G.add_edge(0,i+1,K,0)
    for j in range(N):
        G.add_edge(i+1,N+1+j,1,10**9-A[i][j])

for j in range(N):
    G.add_edge(N+1+j,2*N+1,K,0)

f = G.flow(0,2*N+1,N**2)
print(N*N*10**9-f)

res = [["." for j in range(N)] for i in range(N)]
for i in range(N):
    for w, cap, _, _ in G.G[i+1]:
        if N+1<=w<=2*N:
            j = w - (N+1)
            if cap==0:
                res[i][j] = "X"
for i in range(N):
    print("".join(res[i]))

Submission status: Accepted

Solution code:
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

N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

G = MinCostFlow(2*N+3)
G.add_edge(0,2*N+2,10**18,0)
G.add_edge(2*N+2,2*N+1,10**18,0)

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

for j in range(N):
    G.add_edge(N+1+j,2*N+1,K,0)

f = G.flow(0,2*N+1,N**2)
print(-f)

res = [["." for j in range(N)] for i in range(N)]
for i in range(N):
    for w, cap, _, _ in G.G[i+1]:
        if N+1<=w<=2*N:
            j = w - (N+1)
            if cap==0:
                res[i][j] = "X"
for i in range(N):
    print("".join(res[i]))

Submission status: Accepted

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
    que = []
    dist[s] = 0
    push(que, (0, s))
    while que:
      k, v = pop(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
          push(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__(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: Accepted

Solution code:
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

N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

G = MinCostFlow(N**2+2*N+3)
G.add_edge(0,N**2+2*N+2,10**18,0)
G.add_edge(N**2+2*N+2,N**2+2*N+1,10**18,0)

for i in range(N):
    G.add_edge(0,i+1,K,0)
    for j in range(N):
        node = N * i + j + 2*N + 1
        G.add_edge(i+1,node,1,-A[i][j])
        G.add_edge(node,N+1+j,1,0)

for j in range(N):
    G.add_edge(N+1+j,N**2+2*N+1,K,0)

f = G.flow(0,N**2+2*N+1,N**2)
print(-f)

res = [["." for j in range(N)] for i in range(N)]
for i in range(N):
    for Node,cap,_,_ in G.G[i+1]:
        if Node == 0:
            continue
        node = Node - (2*N+1)
        px,py = node//N,node%N
        if cap==0:
            res[px][py] = "X"

for i in range(N):
    print("".join(res[i]))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

class MinCostFlow():
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, fr, to, cap, cost):
        #assert 0 <= fr < self.n
        #assert 0 <= to < self.n
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap, cost])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0, -cost])
        return m

    def get_edge(self, idx):
        #assert 0 <= idx < len(self.pos)
        to, rev, cap, cost = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap, rev_cost = self.graph[to][rev]
        return self.pos[idx][0], to, cap + rev_cap, rev_cap, cost

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

    def dual_ref(self, s, t):
        dist = [2**63 - 1] * self.n
        dist[s] = 0
        vis = [0] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        queue = []
        heappush(queue, (0, s))
        while queue:
            k, v = heappop(queue)
            if vis[v]: continue
            vis[v] = True
            if v == t: break
            for i in range(len(self.graph[v])):
                to, rev, cap, cost = self.graph[v][i]
                if vis[to] or cap == 0: continue
                cost += self.dual[v] - self.dual[to]
                if dist[to] - dist[v] > cost:
                    dist[to] = dist[v] + cost
                    self.pv[to] = v
                    self.pe[to] = i
                    heappush(queue, (dist[to], 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 flow(self, s, t):
        return self.flow_with_limit(s, t, 2**63 - 1)

    def flow_with_limit(self, s, t, limit):
        return self.slope_with_limit(s, t, limit)[-1]

    def slope(self, s, t):
        return self.slope_with_limit(s, t, 2**63 - 1)

    def slope_with_limit(self, s, t, limit):
        #assert 0 <= s < self.n
        #assert 0 <= t < self.n
        #assert s != t
        flow = 0
        cost = 0
        prev_cost = -1
        res = [(flow, cost)]
        self.dual = [0] * self.n
        while flow < limit:
            if not self.dual_ref(s, t): break
            c = limit - flow
            v = t
            while v != s:
                c = min(c, self.graph[self.pv[v]][self.pe[v]][2])
                v = self.pv[v]
            v = t
            while v != s:
                to, rev, cap, _ = self.graph[self.pv[v]][self.pe[v]]
                self.graph[self.pv[v]][self.pe[v]][2] -= c
                self.graph[v][rev][2] += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                res.pop()
            res.append((flow, cost))
            prev_cost = cost
        return res

MAX = 10**9

N, K = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(N)]

mcf = MinCostFlow(2 * N + 2)

s = 2 * N
t = 2 * N + 1

mcf.add_edge(s, t, N * K, MAX)

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

print(N * K * MAX - mcf.flow_with_limit(s, t, N * K)[1])

res = [['.' for j in range(N)] for i in range(N)]

for fr, to, cap, flow, cost in mcf.edges():
    if flow == 0 or fr == s or to == t:
        continue
    res[fr][to - N] = 'X'

for r in res:
    print(''.join(r))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

class MinCostFlow():
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, fr, to, cap, cost):
        assert 0 <= fr < self.n
        assert 0 <= to < self.n
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap, cost])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0, -cost])
        return m

    def get_edge(self, idx):
        assert 0 <= idx < len(self.pos)
        to, rev, cap, cost = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap, rev_cost = self.graph[to][rev]
        return self.pos[idx][0], to, cap + rev_cap, rev_cap, cost

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

    def dual_ref(self, s, t):
        dist = [2**63 - 1] * self.n
        dist[s] = 0
        vis = [0] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        queue = []
        heappush(queue, (0, s))
        while queue:
            k, v = heappop(queue)
            if vis[v]: continue
            vis[v] = True
            if v == t: break
            for i in range(len(self.graph[v])):
                to, rev, cap, cost = self.graph[v][i]
                if vis[to] or cap == 0: continue
                cost += self.dual[v] - self.dual[to]
                if dist[to] - dist[v] > cost:
                    dist[to] = dist[v] + cost
                    self.pv[to] = v
                    self.pe[to] = i
                    heappush(queue, (dist[to], 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 flow(self, s, t):
        return self.flow_with_limit(s, t, 2**63 - 1)

    def flow_with_limit(self, s, t, limit):
        return self.slope_with_limit(s, t, limit)[-1]

    def slope(self, s, t):
        return self.slope_with_limit(s, t, 2**63 - 1)

    def slope_with_limit(self, s, t, limit):
        assert 0 <= s < self.n
        assert 0 <= t < self.n
        assert s != t
        flow = 0
        cost = 0
        prev_cost = -1
        res = [(flow, cost)]
        self.dual = [0] * self.n
        while flow < limit:
            if not self.dual_ref(s, t): break
            c = limit - flow
            v = t
            while v != s:
                c = min(c, self.graph[self.pv[v]][self.pe[v]][2])
                v = self.pv[v]
            v = t
            while v != s:
                to, rev, cap, _ = self.graph[self.pv[v]][self.pe[v]]
                self.graph[self.pv[v]][self.pe[v]][2] -= c
                self.graph[v][rev][2] += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                res.pop()
            res.append((flow, cost))
            prev_cost = cost
        return res

MAX = 10**9

N, K = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(N)]

mcf = MinCostFlow(2 * N + 2)

s = 2 * N
t = 2 * N + 1

mcf.add_edge(s, t, N * K, MAX)

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

print(N * K * MAX - mcf.flow_with_limit(s, t, N * K)[1])

res = [['.' for j in range(N)] for i in range(N)]

for fr, to, cap, flow, cost in mcf.edges():
    if flow == 0 or fr == s or to == t:
        continue
    res[fr][to - N] = 'X'

for r in res:
    print(''.join(r))