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))