結果
問題 | No.1479 Matrix Eraser |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-14 01:50:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 440 ms / 3,000 ms |
コード長 | 3,623 bytes |
コンパイル時間 | 161 ms |
コンパイル使用メモリ | 81,684 KB |
実行使用メモリ | 135,836 KB |
最終ジャッジ日時 | 2023-10-18 11:26:56 |
合計ジャッジ時間 | 13,980 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 61 ms
68,176 KB |
testcase_01 | AC | 62 ms
68,176 KB |
testcase_02 | AC | 63 ms
68,176 KB |
testcase_03 | AC | 64 ms
68,176 KB |
testcase_04 | AC | 62 ms
68,176 KB |
testcase_05 | AC | 62 ms
68,176 KB |
testcase_06 | AC | 62 ms
68,176 KB |
testcase_07 | AC | 189 ms
85,844 KB |
testcase_08 | AC | 192 ms
91,672 KB |
testcase_09 | AC | 250 ms
102,340 KB |
testcase_10 | AC | 362 ms
118,776 KB |
testcase_11 | AC | 274 ms
108,344 KB |
testcase_12 | AC | 161 ms
87,976 KB |
testcase_13 | AC | 187 ms
91,672 KB |
testcase_14 | AC | 170 ms
88,240 KB |
testcase_15 | AC | 111 ms
79,672 KB |
testcase_16 | AC | 177 ms
89,824 KB |
testcase_17 | AC | 413 ms
131,388 KB |
testcase_18 | AC | 411 ms
131,348 KB |
testcase_19 | AC | 426 ms
131,388 KB |
testcase_20 | AC | 406 ms
131,612 KB |
testcase_21 | AC | 410 ms
131,612 KB |
testcase_22 | AC | 421 ms
131,348 KB |
testcase_23 | AC | 422 ms
131,348 KB |
testcase_24 | AC | 432 ms
131,348 KB |
testcase_25 | AC | 437 ms
131,612 KB |
testcase_26 | AC | 440 ms
131,388 KB |
testcase_27 | AC | 239 ms
91,068 KB |
testcase_28 | AC | 238 ms
91,288 KB |
testcase_29 | AC | 240 ms
91,296 KB |
testcase_30 | AC | 243 ms
91,404 KB |
testcase_31 | AC | 240 ms
91,312 KB |
testcase_32 | AC | 211 ms
124,712 KB |
testcase_33 | AC | 205 ms
123,160 KB |
testcase_34 | AC | 206 ms
124,300 KB |
testcase_35 | AC | 221 ms
133,156 KB |
testcase_36 | AC | 213 ms
124,356 KB |
testcase_37 | AC | 111 ms
96,584 KB |
testcase_38 | AC | 195 ms
90,024 KB |
testcase_39 | AC | 379 ms
135,836 KB |
testcase_40 | AC | 64 ms
68,196 KB |
ソースコード
from collections import defaultdict from typing import List from collections import deque from typing import List, Tuple class Hungarian: """ 軽量化Dinic法 ref : https://snuke.hatenablog.com/entry/2019/05/07/013609 """ @staticmethod def fromEdges(n: int, edges: List[Tuple[int, int]]) -> "Hungarian": """从无向边列表构造""" adjList = [[] for _ in range(n)] for u, v in edges: adjList[u].append(v) adjList[v].append(u) colors, ok = isBipartite(n, adjList) if not ok: raise ValueError("not bipartite") h = Hungarian(n) for u, v in edges: if colors[u] == 1: u, v = v, u h.addEdge(u, v) return h def __init__(self, n: int): self._n = n self._to = [[] for _ in range(n)] def addEdge(self, u: int, v: int) -> None: """男孩u和女孩v连边""" self._to[u].append(v) def work(self) -> List[Tuple[int, int]]: """返回最大匹配""" n, to = self._n, self._to pre = [-1] * n root = [-1] * n p = [-1] * n q = [-1] * n upd = True while upd: upd = False s = [] s_front = 0 for i in range(n): if p[i] == -1: root[i] = i s.append(i) while s_front < len(s): v = s[s_front] s_front += 1 if p[root[v]] != -1: continue for u in to[v]: if q[u] == -1: while u != -1: q[u] = v p[v], u = u, p[v] v = pre[v] upd = True break u = q[u] if pre[u] != -1: continue pre[u] = v root[u] = root[v] s.append(u) if upd: for i in range(n): pre[i] = -1 root[i] = -1 return [(v, p[v]) for v in range(n) if p[v] != -1] def isBipartite(n: int, adjList: List[List[int]]) -> Tuple[List[int], bool]: """二分图检测 bfs染色""" def bfs(start: int) -> bool: colors[start] = 0 queue = deque([start]) while queue: cur = queue.popleft() for next in adjList[cur]: if colors[next] == -1: colors[next] = colors[cur] ^ 1 queue.append(next) elif colors[next] == colors[cur]: return False return True colors = [-1] * n for i in range(n): if colors[i] == -1 and not bfs(i): return [], False return colors, True def solve(grid: List[List[int]]) -> int: ROW, COL = len(grid), len(grid[0]) mp = defaultdict(list) for i in range(ROW): for j in range(COL): mp[grid[i][j]].append((i, j)) res = 0 for v, edges in mp.items(): if v == 0: continue H = Hungarian(len(edges)) id1, id2 = dict(), dict() for u, v in edges: id1.setdefault(u, len(id1)) id2.setdefault(v, len(id2)) H.addEdge(id1[u], id2[v]) res += len(H.work()) return res if __name__ == "__main__": n, m = map(int, input().split()) grid = [list(map(int, input().split())) for _ in range(n)] print(solve(grid))