結果

問題 No.1479 Matrix Eraser
ユーザー toyuzukotoyuzuko
提出日時 2021-04-17 18:27:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 907 ms / 3,000 ms
コード長 4,075 bytes
コンパイル時間 530 ms
コンパイル使用メモリ 87,408 KB
実行使用メモリ 173,220 KB
最終ジャッジ日時 2023-09-17 03:50:56
合計ジャッジ時間 23,690 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
80,728 KB
testcase_01 AC 91 ms
80,836 KB
testcase_02 AC 94 ms
80,628 KB
testcase_03 AC 92 ms
80,704 KB
testcase_04 AC 91 ms
80,732 KB
testcase_05 AC 89 ms
80,796 KB
testcase_06 AC 88 ms
80,788 KB
testcase_07 AC 377 ms
103,876 KB
testcase_08 AC 406 ms
105,616 KB
testcase_09 AC 579 ms
110,480 KB
testcase_10 AC 754 ms
119,748 KB
testcase_11 AC 621 ms
113,636 KB
testcase_12 AC 391 ms
104,596 KB
testcase_13 AC 412 ms
105,328 KB
testcase_14 AC 371 ms
105,020 KB
testcase_15 AC 230 ms
100,584 KB
testcase_16 AC 385 ms
107,548 KB
testcase_17 AC 883 ms
121,708 KB
testcase_18 AC 906 ms
124,808 KB
testcase_19 AC 885 ms
123,420 KB
testcase_20 AC 880 ms
121,128 KB
testcase_21 AC 877 ms
121,716 KB
testcase_22 AC 883 ms
124,076 KB
testcase_23 AC 872 ms
122,160 KB
testcase_24 AC 873 ms
121,544 KB
testcase_25 AC 881 ms
121,680 KB
testcase_26 AC 907 ms
123,776 KB
testcase_27 AC 678 ms
135,584 KB
testcase_28 AC 625 ms
134,520 KB
testcase_29 AC 640 ms
135,560 KB
testcase_30 AC 684 ms
136,644 KB
testcase_31 AC 614 ms
134,392 KB
testcase_32 AC 430 ms
170,512 KB
testcase_33 AC 407 ms
167,260 KB
testcase_34 AC 414 ms
173,220 KB
testcase_35 AC 429 ms
171,316 KB
testcase_36 AC 432 ms
170,452 KB
testcase_37 AC 131 ms
104,516 KB
testcase_38 AC 532 ms
134,532 KB
testcase_39 AC 777 ms
123,872 KB
testcase_40 AC 88 ms
80,880 KB
権限があれば一括ダウンロードができます

ソースコード

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