結果

問題 No.1479 Matrix Eraser
ユーザー toyuzukotoyuzuko
提出日時 2021-04-17 18:27:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 933 ms / 3,000 ms
コード長 4,075 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 171,668 KB
最終ジャッジ日時 2024-07-04 01:31:25
合計ジャッジ時間 24,498 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

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

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

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

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

    def dfs(self, s, t, up):
        stack = [t]
        while stack:
            v = stack.pop()
            if v == s:
                flow = up
                for v in stack:
                    to, rev, cap = self.graph[v][self.iter[v]]
                    flow = min(flow, self.graph[to][rev][2])
                for v in stack:
                    self.graph[v][self.iter[v]][2] += flow
                    to, rev, cap = self.graph[v][self.iter[v]]
                    self.graph[to][rev][2] -= flow
                return flow
            lv = self.level[v]
            for i in range(self.iter[v], len(self.graph[v])):
                to, rev, cap = self.graph[v][i]
                if lv > self.level[to] and self.graph[to][rev][2]:
                    self.iter[v] = i
                    stack.append(v)
                    stack.append(to)
                    break
            else:
                self.iter[v] = len(self.graph[v])
                self.level[v] = self.n
        return 0

    def max_flow(self, s, t):
        return self.max_flow_with_limit(s, t, 2**63 - 1)

    def max_flow_with_limit(self, s, t, limit):
        flow = 0
        while flow < limit:
            self.level = [-1] * self.n
            self.level[s] = 0
            queue = deque()
            queue.append(s)
            while queue:
                v = queue.popleft()
                for to, rev, cap in self.graph[v]:
                    if cap == 0 or self.level[to] >= 0: continue
                    self.level[to] = self.level[v] + 1
                    if to == t: break
                    queue.append(to)
            if self.level[t] == -1: break
            self.iter = [0] * self.n
            while flow < limit:
                f = self.dfs(s, t, limit - flow)
                if not f: break
                flow += f
        return flow

class BipartiteMatching():
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.mf = MaxFlow(l + r + 2)
        for i in range(l):
            self.mf.add_edge(l + r, i, 1)
        for i in range(r):
            self.mf.add_edge(i + l, l + r + 1, 1)

    def add_edge(self, u, v):
        self.mf.add_edge(u, v + self.l, 1)

    def matching(self):
        m = self.mf.max_flow(self.l + self.r, self.l + self.r + 1)
        self.match_l = [-1] * self.l
        self.match_r = [-1] * self.r
        for fr, to, cap, flow in self.mf.edges():
            if flow == 0 or fr == self.l + self.r or to == self.l + self.r + 1:
                continue
            self.match_l[fr] = to - self.l
            self.match_r[to - self.l] = fr
        return m

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

idx = [[] for _ in range(5 * 10**5 + 1)]

for i in range(H):
    for j in range(W):
        idx[A[i][j]].append(i * W + j)

res = 0

for i in range(1, 5 * 10**5 + 1)[::-1]:
    if not idx[i]: continue
    sx = []
    sy = []
    for z in idx[i]:
        x, y = divmod(z, W)
        sx.append(x)
        sy.append(y)
    cx = {v : k for k, v in enumerate(sorted(set(sx)))}
    cy = {v : k for k, v in enumerate(sorted(set(sy)))}
    lx = len(cx)
    ly = len(cy)
    bm = BipartiteMatching(lx, ly)
    for z in idx[i]:
        x, y = divmod(z, W)
        bm.add_edge(cx[x], cy[y])
    res += bm.matching()

print(res)
0