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):
N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

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

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

    def get_edges(self):
        ret = []
        for fr,i in self.pos:
            to,rev,cap,cost = self.es[fr][i]
            flow = self.es[to][rev][2]
            cap += flow
            ret.append((fr, to, cap, flow, cost))
        return ret

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

    def slope(self, s, t, flow_limit=2**63):
        self.dual = [0] * self.n
        self.dist = [2**63] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        self.vis = [False] * self.n
        def _dual_ref():
            self.dist = [2**63] * self.n
            self.pv = [-1] * self.n
            self.pe = [-1] * self.n
            self.vis = [False] * self.n
            hq = [(0,s)]
            self.dist[s] = 0
            while hq:
                p = heapq.heappop(hq)
                v = p[1]
                if self.vis[v]: continue
                self.vis[v] = True
                if v==t: break
                for i,(to,rev,cap,cost) in enumerate(self.es[v]):
                    if self.vis[to] or not cap: continue
                    _cost = cost - self.dual[to] + self.dual[v]
                    if self.dist[to] - self.dist[v] > _cost:
                        self.dist[to] = self.dist[v] + _cost
                        self.pv[to] = v
                        self.pe[to] = i
                        heapq.heappush(hq, (self.dist[to],to))
            if not self.vis[t]:
                return False
            for v in range(self.n):
                if not self.vis[v]: continue
                self.dual[v] -= self.dist[t] - self.dist[v]
            return True
        flow, cost, prev_cost = 0, 0, -1
        ret = [(flow, cost)]
        while flow < flow_limit:
            if not _dual_ref(): break
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.es[self.pv[v]][self.pe[v]][2])
                v = self.pv[v]
            v = t
            while v != s:
                self.es[self.pv[v]][self.pe[v]][2] -= c
                self.es[v][self.es[self.pv[v]][self.pe[v]][1]][2] += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                ret.pop()
            ret.append((flow, cost))
            prev_cost = cost
        return ret

mcf = MinCostFlow(2*N + 2)
src,dst = 2*N, 2*N+1

BIG = 10**9
mcf.add_edge(src, dst, N*K, BIG)
for i in range(N):
    mcf.add_edge(src, i, K, 0)
    mcf.add_edge(N+i, dst, K, 0)
for i,row in enumerate(A):
    for j,a in enumerate(row):
        mcf.add_edge(i, N+j, 1, BIG - a)

_,mincost = mcf.flow(src, dst, N*K)
ans = [['.']*N for _ in range(N)]
print(N*K*BIG - mincost)
for fr,to,cap,flow,cost in mcf.get_edges():
    if fr == src or to == dst or flow == 0: continue
    ans[fr][to - N] = 'X'
for row in ans:
    print(''.join(row))

Solution (Python):





from heapq import heappop, heappush
class mcf_graph:
    numeric_limits_max = 10 ** 18

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

    def add_edge(self, _from: int, _to: int, cap: int, cost: int) -> int:
        assert 0 <= _from and _from < self._n
        assert 0 <= _to and _to < self._n
        m = len(self.pos)
        self.pos.append((_from, len(self.g[_from])))
        self.g[_from].append(self._edge(_to, len(self.g[_to]), cap, cost))
        self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0, -cost))
        return m
    
    class edge:
        def __init__(s, _from: int, _to: int, cap: int, flow: int, cost: int):
            s._from = _from; s._to = _to; s.cap = cap; s.flow = flow; s.cost = cost
    
    def get_edge(self, i: int) -> edge:
        m = len(self.pos)
        assert 0 <= i and i < m
        _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) -> list:
        m = len(self.pos)
        result = [self.get_edge(i) for i in range(m)]
        return result
    
    def flow(self, s: int, t: int) -> edge:
        return self.flow_(s, t, self.numeric_limits_max)
    def flow_(self, s: int, t: int, flow_limit: int) -> edge:
        return self.__slope(s, t, flow_limit)[-1]
    
    def slope(self, s: int, t: int) -> list:
        return self.slope_(s, t, self.numeric_limits_max)
    def slope_(self, s: int, t: int, flow_limit: int) -> list:
        return self.__slope(s, t, flow_limit)
    
    def __slope(self, s: int, t: int, flow_limit: int) -> list:
        assert 0 <= s and s < self._n
        assert 0 <= t and t < self._n
        assert s != t
        dual = [0] * self._n; dist = [0] * self._n
        pv, pe = [-1] * self._n, [-1] * self._n
        vis = [False] * self._n
        
        def dual_ref():
            for i in range(self._n):
                dist[i] = self.numeric_limits_max
                pv[i] = -1
                pe[i] = -1
                vis[i] = False
            class Q:
                def __init__(s, key: int, to: int):
                    s.key = key; s.to = to
                def __lt__(s, r): return s.key < r.key
            que = []
            dist[s] = 0
            heappush(que, Q(0, s))
            while que:
                v = heappop(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
                        heappush(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 = 0; prev_cost = -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: int, rev: int, cap: int, cost: int):
            s.to = to; s.rev = rev; s.cap = cap; s.cost = cost
        

import sys









MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, k = read_ints()
    a = [read_int_list() for _ in range(n)]
    mcf = mcf_graph(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(i + n, t, k, 0)
    mcf.add_edge(s, t, n * k, INF)
    
    for i in range(n):
        for j in range(n):
            mcf.add_edge(i, n + j, 1, INF - a[i][j])
    
    result = mcf.flow_(s, t, n * k)
    print(n * k * INF - result[1])
    grid = [['.'] * n for _ in range(n)]
    edges = mcf.edges()
    for e in edges:
        if e._from == s or e._to == t or e.flow == 0: continue
        grid[e._from][e._to - n] = 'X'
    print(*[''.join(g) for g in grid], sep='\n')

if __name__ == '__main__':
    Main()

Solution (Python):
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:
    """ 最小費用流(ベルマンフォード版、負コストに対応可)：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]]
        
        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

mcf.add_edge(s, t, N*N, 0)
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 = -mcf.flow(s, t, N*N)
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]))

Solution (Python):
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]]
        
        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()

offset = 10**12
mcf = MinCostFlow(N*2+2)
s = N*2
t = N*2 + 1

mcf.add_edge(s, t, N*N, offset)
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, offset-grid[i][j])

mn = mcf.flow(s, t, N*N)
mn -= offset*N*N
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]))

Solution (Python):
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:
    """ 最小費用流(ダイクストラ版)：O(F*E*logV) """

    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):
        from heapq import heappush, heappop

        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
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (to, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[to] > dist[v] + cost + H[v] - H[to]:
                        dist[to] = r = dist[v] + cost + H[v] - H[to]
                        prv_v[to] = v; prv_e[to] = i
                        heappush(que, (r, to))
            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]]
        
        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()

offset = 10**12
mcf = MinCostFlow(N*2+2)
s = N*2
t = N*2 + 1

mcf.add_edge(s, t, N*N, offset)
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, offset-grid[i][j])

mn = mcf.flow(s, t, N*N)
mn -= offset*N*N
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]))

Solution (Python):
from heapq import heappush, heappop
class MinCostFlow_by_Dijkstra:
    
    
    INF = float("inf")

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

    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)
        self.E.add((fr,to))

    def flow(self, s, t, f,Mode=False):
        N = self.N; G = self.G
        INF = MinCostFlow_by_Dijkstra.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]

        if Mode:
            R={}
            for v in range(self.N):
                R[v]={}
                for S in self.G[v]:
                    w=S[0]
                    if (v,w) in self.E:
                        R[v][w]=S[-1][1]

            return res,R
        else:
            return res

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

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

inf=float("inf")
huge=10**18

D=MinCostFlow_by_Dijkstra(2*N+2)
s=2*N
t=2*N+1

for i in range(N):
    D.add_edge(s,i,K,0)
    D.add_edge(N+i,t,K,0)
D.add_edge(s,t,N*K,huge)

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

p,R=D.flow(s,t,N*K,True)
p=huge*N*K-p

S=[["."]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if R[i][N+j]==1:
            S[i][j]="X"

T=["".join(a) for a in S]

print(p)
print("\n".join(T))

Solution (Python):




import heapq

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

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

Solution (Python):
import os
import sys
from heapq import heappop, heappush

import numpy as np


def solve(n, k, aaa):
    MINCOSTFLOW_LINKS = []
    MINCOSTFLOW_LINK_INDICES = []
    MINCOSTFLOW_CURRENT_LINK_INDEX = []
    INF = 10 ** 10

    def mincostflow_init(m):
        """ m:辺数(逆辺除く) """
        MINCOSTFLOW_LINKS.append(np.zeros((m * 2, 5), np.int64))
        MINCOSTFLOW_CURRENT_LINK_INDEX.append(0)
        return len(MINCOSTFLOW_LINKS) - 1

    def mincostflow_add_link(ins, frm, to, capacity, cost):
        links = MINCOSTFLOW_LINKS[ins]
        li = MINCOSTFLOW_CURRENT_LINK_INDEX[ins]
        links[li] = (frm, to, capacity, cost, li + 1)
        links[li + 1] = (to, frm, 0, -cost, li)
        MINCOSTFLOW_CURRENT_LINK_INDEX[ins] += 2

    def mincostflow_fix_link(ins, n):
        links = MINCOSTFLOW_LINKS[ins]
        sort_idx = np.argsort(links[:, 0])
        links[links[sort_idx, 4], 4] = np.arange(sort_idx.size)
        links = links[sort_idx]

        MINCOSTFLOW_LINK_INDICES.append(np.searchsorted(links[:, 0], np.arange(n + 1)))
        MINCOSTFLOW_LINKS[ins] = links

    def mincostflow_flow(ins, s, t, quantity):
        links = MINCOSTFLOW_LINKS[ins]
        link_indices = MINCOSTFLOW_LINK_INDICES[ins]
        n = len(links)
        res = 0
        potentials = np.zeros(n, dtype=np.int64)
        dist = np.full(n, INF, dtype=np.int64)
        prev_v = np.full(n, -1, dtype=np.int64)
        prev_e = np.full(n, -1, dtype=np.int64)

        while quantity:
            dist.fill(INF)
            dist[s] = 0
            que = [(0, s)]

            while que:
                total_cost, v = heappop(que)
                if dist[v] < total_cost:
                    continue
                for li in range(link_indices[v], link_indices[v + 1]):
                    _, u, cap, cost, _ = links[li]
                    new_cost = dist[v] + potentials[v] - potentials[u] + cost
                    if cap > 0 and new_cost < dist[u]:
                        dist[u] = new_cost
                        prev_v[u] = v
                        prev_e[u] = li
                        heappush(que, (new_cost, u))

            
            if dist[t] == INF:
                return -1

            potentials += dist

            cur_flow = quantity
            v = t
            while v != s:
                cur_flow = min(cur_flow, links[prev_e[v]][2])
                v = prev_v[v]
            quantity -= cur_flow
            res += cur_flow * potentials[t]

            v = t
            while v != s:
                link = links[prev_e[v]]
                link[2] -= cur_flow
                links[link[4]][2] += cur_flow
                v = prev_v[v]

        return res

    ins = mincostflow_init(n ** 2 + n * 2 + 1)
    s = n + n
    t = s + 1

    mincostflow_add_link(ins, s, t, n * k, INF)
    for i in range(n):
        mincostflow_add_link(ins, s, i, k, 0)
        mincostflow_add_link(ins, i + n, t, k, 0)
        for j in range(n):
            mincostflow_add_link(ins, i, j + n, 1, INF - aaa[i][j])
    mincostflow_fix_link(ins, n * 2 + 2)

    ans = INF * (n * k) - mincostflow_flow(ins, s, t, n * k)

    matrix = np.zeros((n, n), dtype=np.int8)
    links = MINCOSTFLOW_LINKS[ins]
    link_indices = MINCOSTFLOW_LINK_INDICES[ins]
    for i in range(n):
        for li in range(link_indices[i], link_indices[i + 1]):
            link = links[li]
            if link[1] == t or link[2] == 1 or link[3] <= 0:
                continue
            j = link[1] - n
            matrix[i][j] = 1

    return ans, matrix


SIGNATURE = '(i8,i8,i8[:,:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

n, k = map(int, sys.stdin.readline().split())
aaa = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ').reshape(n, n)
ans, matrix = solve(n, k, aaa)

sys.stdout.buffer.write((str(ans) + '\n').encode())
np.savetxt(sys.stdout.buffer, np.vectorize('.X'.__getitem__)(matrix), fmt='%s', delimiter='')

Solution (Python):
import networkx as nx
from networkx.algorithms.flow import network_simplex

MAX = 10**9
n, k = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
s, t = 2 * n, 2 * n + 1

G = nx.DiGraph()
G.add_node(s, demand=-n*k)
G.add_node(t, demand=n*k)
G.add_edge(s, t, weight=MAX, capacity=n*k)

for i in range(n):
	G.add_edge(s, i, weight=0, capacity=k)
	G.add_edge(n + i, t, weight=0, capacity=k)
	for j in range(n):
		G.add_edge(i, n + j, weight=MAX-a[i][j], capacity=1)

flow_cost, flow_dict = network_simplex(G)
print(n * k * MAX - flow_cost)

ans = [["." for _ in range(n)] for _ in range(n)]
for fr in flow_dict.keys():
	if 0 <= fr < n:
		for to, flow in flow_dict[fr].items():
			if flow == 1:
				ans[fr][to - n] = "X"

print(*["".join(x) for x in ans], sep="\n")