Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

C - Decoding Ancient Messages

Problem Statement

Professor Y's work is to dig up ancient artifacts. Recently, he found a lot of strange stone plates, each of which has $N^2$ characters arranged in an $N \times N$ matrix. Further research revealed that each plate represents a message of length $N$. Also, the procedure to decode the message from a plate was turned out to be the following:

Select $N$ characters from the plate one by one so that any two characters are neither in the same row nor in the same column.

Create a string by concatenating the selected characters.

Among all possible strings obtained by the above steps, find the lexicographically smallest one. It is the message represented by this plate.

NOTE: The order of the characters is defined as the same as the order of their ASCII values (that is, $\mathtt{A} \lt \mathtt{B} \lt \cdots \lt \mathtt{Z} \lt \mathtt{a} \lt \mathtt{b} \lt \cdots \lt \mathtt{z}$).

After struggling with the plates, Professor Y gave up decoding messages by hand. You, a great programmer and Y's old friend, was asked for a help. Your task is to write a program to decode the messages hidden in the plates.

Input

The input is formated as follows:

$N$
$c_{11} c_{12} \cdots c_{1N}$
$c_{21} c_{22} \cdots c_{2N}$
:
:
$c_{N1} c_{N2} \cdots c_{NN}$

The first line contains an integer $N$ ($1 \le N \le 50$). Each of the subsequent $N$ lines contains a string of $N$ characters. Each character in the string is an uppercase or lowercase English letter (A-Z, a-z).

Output

Print the message represented by the plate in a line.

Sample Input 1

3
aab
czc
baa

Output for the Sample Input 1

aac

Sample Input 2

36
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiQiiiiiiiiiiiiiiiQiiiiiiiii
iiiiiiiiiiQQQiiiiiiiiiiQQQQiiiiiiiii
iiiiiiiiiiQQQQQiiiiiiiQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQiiiiiiiiiii
iiiiiiiiiiiiQQQQQQQQQQQQQiiiiiiiiiii
iiiiiiiiiiiQQQQQQQQQQQQQQQiiiiiiiiii
iiiiiiiiiiQQQQQQQQQQQQQQQQQiiiiiiiii
iiiiiiQiiiQQQQQQQQQQQQQQQQQiiiQiiiii
iiiiiiQQiQQQQQQQQQQQQQQQQQQiiQQiiiii
iiiiiiiQQQQQQQQQQQQQQQQQQQQiQQiiiiii
iiiiiiiiiQQQQQQQQQQQQQQQQQQQQiiiiiii
iiiiiiiiQQQQQiiQQQQQQQQiiQQQQQiiiiii
iiiiiiQQQQQQiiiiQQQQQiiiiQQQQQQiiiii
iiiiiQQQQQQQQiiiQQQQQiiQQQQQQQQiQiii
iiiQQQQQQQiiQiiiQQQQQiiQiiQQQQQQQQii
iQQQQQQQQQiiiiiQQQQQQQiiiiiiQQQQQQQi
iiQQQQQQQiiiiiiQQQQQQQiiiiiiiiQQQiii
iQQQQiiiiiiiiiQQQQQQQQQiiiiiiiiQQQii
iiiiiiiiiiiiiiQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiQQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiQQQQQQQQQQiiiiiiiiiiiii
iiiiiiiiiiiiiiQQQQQQQQiiiiiiiiiiiiii
iiiiiiiiiiiiiiQQQQQQQQiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

Output for the Sample Input 2

QQQQQQQQQQQQQQQQQQQQQQQQQiiiiiiiiiii

Sample Input 3

3
Acm
aCm
acM

Output for the Sample Input 3

ACM


Sample input:
3
aab
czc
baa


Sample output:
aac

Submission status: Wrong Answer

Solution code:
import heapq

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

class min_cost_flow:
    INF = 52**60
    def __init__(self, n):
        self.V = n
        self.G = [[] for _ in range(n)]
        self.h = [0 for _ in range(n)]
        self.dist = [0 for _ in range(n)]

    def add_edge(self, f, t, cap, cost):
        self.G[f].append(edge(t,cap,cost,len(self.G[t])))
        self.G[t].append(edge(f,0,-cost,len(self.G[f])-1))

    def min_cost_flow(self, s, t, f):
        prevv = [0 for _ in range(self.V)]
        preve = [0 for _ in range(self.V)]

        res = 0
        self.h = [0 for _ in range(self.V)]
        while f > 0:
            pq = []
            self.dist = [min_cost_flow.INF for _ in range(self.V)]
            self.dist[s] = 0
            # dijkstra
            heapq.heappush(pq,(0,s))
            while len(pq) != 0:
                p = heapq.heappop(pq)
                v = p[1]
                if p[0] > self.dist[v]:
                    continue
                for i in range(len(self.G[v])):
                    e = self.G[v][i]
                    if e.cap>0 and self.dist[e.to]>self.dist[v]+e.cost+self.h[v]-self.h[e.to]:
                        self.dist[e.to] =  self.dist[v]+e.cost+self.h[v]-self.h[e.to]
                        prevv[e.to] = v
                        preve[e.to] = i
                        heapq.heappush(pq,(self.dist[e.to],e.to))

            if self.dist[t] == min_cost_flow.INF:
                return -1

            for i in range(self.V):
                self.h[i] += self.dist[i]

            d = f
            v = t
            while v != s:
                d = min(d,self.G[prevv[v]][preve[v]].cap)
                v = prevv[v]
            f -= d
            res += d*self.h[t]

            v = t
            while v != s:
                self.G[prevv[v]][preve[v]].cap -= d
                self.G[v][self.G[prevv[v]][preve[v]].rev].cap += d
                v = prevv[v]

        return res

    def solve(self,s,t,n,d):
        f = self.min_cost_flow(s,t,n)
        ans = []
        for i in range(n):
            for j in range(len(self.G[n+i])):
                if self.G[n+i][j].cap>0:
                    cost = -self.G[n+i][j].cost
                    ans.append(d[cost])
                    break
        ans.sort()
        return ''.join(ans)

def main():
    n = int(input())
    s = []
    for _ in range(n):
        s.append(input())

    flow = min_cost_flow(2*n+2)
    S,T = 2*n,2*n+1
    X = 52**52

    for i in range(n):
        flow.add_edge(S,i,1,0)
        flow.add_edge(n+i,T,1,0)

    d = {}
    for i in range(n):
        for j in range(n):
            cost = X
            if 'A'<=s[i][j]<='Z':
                cost -= 52**(51-(ord(s[i][j])-ord(('A'))))
            else:
                cost -= 52**(26-(ord(s[i][j])-ord(('a'))))
            flow.add_edge(i,n+j,1,cost)
            d[cost] = s[i][j]

    print(flow.solve(S,T,n,d))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

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

class min_cost_flow:
    INF = 52**60
    def __init__(self, n):
        self.V = n
        self.G = [[] for _ in range(n)]
        self.h = [0 for _ in range(n)]
        self.dist = [0 for _ in range(n)]

    def add_edge(self, f, t, cap, cost):
        self.G[f].append(edge(t,cap,cost,len(self.G[t])))
        self.G[t].append(edge(f,0,-cost,len(self.G[f])-1))

    def min_cost_flow(self, s, t, f):
        prevv = [0 for _ in range(self.V)]
        preve = [0 for _ in range(self.V)]

        res = 0
        self.h = [0 for _ in range(self.V)]
        while f > 0:
            pq = []
            self.dist = [min_cost_flow.INF for _ in range(self.V)]
            self.dist[s] = 0
            # dijkstra
            heapq.heappush(pq,(0,s))
            while len(pq) != 0:
                p = heapq.heappop(pq)
                v = p[1]
                if p[0] > self.dist[v]:
                    continue
                for i in range(len(self.G[v])):
                    e = self.G[v][i]
                    if e.cap>0 and self.dist[e.to]>self.dist[v]+e.cost+self.h[v]-self.h[e.to]:
                        self.dist[e.to] =  self.dist[v]+e.cost+self.h[v]-self.h[e.to]
                        prevv[e.to] = v
                        preve[e.to] = i
                        heapq.heappush(pq,(self.dist[e.to],e.to))

            if self.dist[t] == min_cost_flow.INF:
                return -1

            for i in range(self.V):
                self.h[i] += self.dist[i]

            d = f
            v = t
            while v != s:
                d = min(d,self.G[prevv[v]][preve[v]].cap)
                v = prevv[v]
            f -= d
            res += d*self.h[t]

            v = t
            while v != s:
                self.G[prevv[v]][preve[v]].cap -= d
                self.G[v][self.G[prevv[v]][preve[v]].rev].cap += d
                v = prevv[v]

        return res

    def solve(self,s,t,n,d):
        f = self.min_cost_flow(s,t,n)
        ans = []
        for i in range(n):
            for j in range(len(self.G[n+i])):
                if self.G[n+i][j].cap>0:
                    cost = -self.G[n+i][j].cost
                    ans.append(d[cost])
                    break
        ans.sort()
        return ''.join(ans)

def main():
    n = int(input())
    s = []
    for _ in range(n):
        s.append(input())

    flow = min_cost_flow(2*n+2)
    S,T = 2*n,2*n+1
    X = 52**52

    for i in range(n):
        flow.add_edge(S,i,1,0)
        flow.add_edge(n+i,T,1,0)

    d = {}
    for i in range(n):
        for j in range(n):
            cost = X
            if 'A'<=s[i][j]<='Z':
                cost -= 52**(51-(ord(s[i][j])-ord(('A'))))
            else:
                cost -= 52**(25-(ord(s[i][j])-ord(('a'))))
            flow.add_edge(i,n+j,1,cost)
            d[cost] = s[i][j]

    print(flow.solve(S,T,n,d))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from string import ascii_lowercase, ascii_uppercase
import sys
readline = sys.stdin.readline
write = sys.stdout.write

from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**100

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]
        self.D = {}

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])
        self.D[fr, to] = G[fr][-1]
        self.D[to, fr] = G[to][-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
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v; prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1

            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

cs = ascii_uppercase + ascii_lowercase
L = len(cs)
def solve():
    N = int(readline())

    g = N*2
    mcf = MinCostFlow(N*2+2)
    for i in range(N):
        mcf.add_edge(g, i, 1, 0)
        mcf.add_edge(N+i, g+1, 1, 0)

    S = []
    for i in range(N):
        *Si, = map(cs.index, readline().strip())
        for j in range(N):
            mcf.add_edge(i, j+N, 1, -L**(L-Si[j]))
        S.append(Si)

    mcf.flow(g, g+1, N)
    ans = []
    for i in range(N):
        Si = S[i]
        for j in range(N):
            if mcf.D[i, j+N][1] == 0:
                ans.append(Si[j])
    ans.sort()

    write("".join(map(cs.__getitem__, ans)))
    write("\n")
solve()