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: Wrong Answer

Solution code:
import heapq

class mcf_graph:


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


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


    class edge:
        def __init__(self, from_, to, cap, flow, cost):
            self.from_ = from_
            self.to = to
            self.cap = cap
            self.flow = flow
            self.cost = cost


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


    def edges(self):
        ret = []
        for i in range(len(self.pos)):
            _e = self.g[self.pos[i][0]][self.pos[i][1]]
            _re = self.g[_e.to][_e.rev]
            ret.append(self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost))
        return ret


    def slope(self, s, t, flow_limit=float('inf')):
        assert 0 <= s < self.n
        assert 0 <= t < self.n
        assert s != t
        
        dual = [0] * self.n
        dist = [float('inf')] * self.n
        pv = [-1] * self.n
        pe = [-1] * self.n
        vis = [False] * self.n

        def _dual_ref():
            nonlocal dual, dist, pv, pe, vis
            dist = [float('inf')] * self.n
            pv = [-1] * self.n
            pe = [-1] * self.n
            vis = [False] * self.n

            que = [(0, s)]
            dist[s] = 0
            while que:
                _, v = heapq.heappop(que)
                if vis[v]:
                    continue
                vis[v] = True
                if v == t:
                    break
                for i in range(len(self.g[v])):
                    e = self.g[v][i]
                    if vis[e.to] or e.cap == 0:
                        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
                        heapq.heappush(que, (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 = [(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


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

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


BIG = 10 ** 9

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

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):
    As = map(int, input().split())
    for j, A in enumerate(As):
        g.add_edge(i, N + j, 1, BIG - A)

result = g.flow(s, t, N * K)

print(N * K * BIG - result[1])

grid = [['.' for _ in range(N)] for _ in range(N)]
edges = g.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'

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from heapq import heappop, heappush, heapify
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


# MinCostFlow
# derived: https://atcoder.jp/contests/practice2/submissions/16726003

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


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, data, K):
    mcf = MinCostFlow(2 * N + 2)
    start = 2 * N
    goal = 2 * N + 1
    mcf.add_edge(start, goal, N * K, INF)
    mcf.add_edge(start, goal, N * K, 0)

    for i in range(N):
        mcf.add_edge(start, i, K, 0)
        mcf.add_edge(i + N, goal, K, 0)
        for j in range(N):
            mcf.add_edge(i, j + N, 1, INF - data[i][j])

    print(N * K * INF - mcf.flow_with_limit(start, goal, N * K)[1])

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

    for frm, to, _cap, flow, _cost in mcf.edges():
        if flow == 0 or frm == start or to == goal:
            continue
        ret[frm][to - N] = 'X'

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


def main():
    # parse input
    N, K = map(int, input().split())
    data = []
    for _i in range(N):
        data.append(list(map(int, input().split())))

    solve(N, data, K)


# tests
T1 = """
3 1
5 3 2
1 4 8
7 6 9
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
19
X..
..X
.X.
"""

T2 = """
3 2
10 10 1
10 10 1
1 1 10
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
50
XX.
XX.
..X
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from heapq import heappop, heappush, heapify
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


# MinCostFlow
# derived: https://atcoder.jp/contests/practice2/submissions/16726003

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


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, data, K):
    mcf = MinCostFlow(2 * N + 2)
    start = 2 * N
    goal = 2 * N + 1
    # mcf.add_edge(start, goal, N * K, INF)
    mcf.add_edge(start, goal, N * K, 0)

    for i in range(N):
        mcf.add_edge(start, i, K, 0)
        mcf.add_edge(i + N, goal, K, 0)
        for j in range(N):
            # mcf.add_edge(i, j + N, 1, INF - data[i][j])
            mcf.add_edge(i, j + N, 1, -data[i][j])

    # print(N * K * INF - mcf.flow_with_limit(start, goal, N * K)[1])
    print(-mcf.flow_with_limit(start, goal, N * K)[1])

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

    for frm, to, _cap, flow, _cost in mcf.edges():
        if flow == 0 or frm == start or to == goal:
            continue
        ret[frm][to - N] = 'X'

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


def main():
    # parse input
    N, K = map(int, input().split())
    data = []
    for _i in range(N):
        data.append(list(map(int, input().split())))

    solve(N, data, K)


# tests
T1 = """
3 1
5 3 2
1 4 8
7 6 9
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
19
X..
..X
.X.
"""

T2 = """
3 2
10 10 1
10 10 1
1 1 10
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
50
XX.
XX.
..X
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Wrong Answer

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

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

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.dual = [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 not cap: 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)]
        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 = [tuple(map(int, input().split())) for _ in range(N)]

MAX = 10**9

mcf = MinCostFlow(2 * N + 2)
mcf.add_edge(2 * N, 2 * N + 1, N * K, MAX)

for i in range(N):
    mcf.add_edge(2 * N, i, K, 0)
    mcf.add_edge(i + N, 2 * N + 1, 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(2 * N, 2 * N + 1, 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 == 2 * N or to == 2 * N + 1:
        continue
    res[fr][to - N] = 'X'

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

Submission status: Wrong Answer

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.dual = [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 not cap: 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 = []
        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 = [tuple(map(int, input().split())) for _ in range(N)]

MAX = 10**18

mcf = MinCostFlow(2 * N + 2)
mcf.add_edge(2 * N, 2 * N + 1, N * K, MAX)

for i in range(N):
    mcf.add_edge(2 * N, i, K, 0)
    mcf.add_edge(i + N, 2 * N + 1, 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(2 * N, 2 * N + 1, 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 == 2 * N or to == 2 * N + 1:
        continue
    res[fr][to - N] = 'X'

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

Submission status: Wrong Answer

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.dual = [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 not cap: 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 = []
        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 = [tuple(map(int, input().split())) for _ in range(N)]

MAX = 10**10

mcf = MinCostFlow(2 * N + 2)
mcf.add_edge(2 * N, 2 * N + 1, N * K, MAX)

for i in range(N):
    mcf.add_edge(2 * N, i, K, 0)
    mcf.add_edge(i + N, 2 * N + 1, 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(2 * N, 2 * N + 1, 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 == 2 * N or to == 2 * N + 1:
        continue
    res[fr][to - N] = 'X'

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