package yukicoder; import java.util.Scanner; import java.util.List; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; public class No1479_2 { private static class Values { public HashMap di, dj; public List ij; public Values() { di = new HashMap (); dj = new HashMap (); ij = new ArrayList(); } } private static int V; private static int[] match; private static boolean[] used; private static List> G; private static void add_edge(int u, int v) { G.get(u).add(v); G.get(v).add(u); } private static boolean dfs(int v) { used[v] = true; for (int u : G.get(v)) { int w = match[u]; if (w < 0 || !used[w] && dfs(w)) { match[v] = u; match[u] = v; return true; } } return false; } private static int bipartite_matching() { int res = 0; match = new int[V]; Arrays.fill(match, -1); for (int v=0; v < V; v++) { if (match[v] < 0) { used = new boolean[V]; if (dfs(v)) { res++; } } } return res; } private static int mpc(int h, int w) { int res = bipartite_matching(); boolean[] matched = new boolean[h]; for (int i=h; i < h+w; i++) { int v = match[i]; if (v >= 0) { matched[v] = true; } } int left = h, right = 0; for (int v = 0; v < h; v++) { if (!matched[v]) { left--; for (int u : G.get(v)) { right++; if (match[u] >= 0) { left--; } } } } return left + right; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int H = scan.nextInt(); int W = scan.nextInt(); HashMap S = new HashMap(); for (int i=0; i < H; i++) { for (int j=0; j < W; j++) { int a = scan.nextInt(); if (a > 0) { if (!S.containsKey(a)) { Values v = new Values(); v.di.put(i, 0); v.dj.put(j, 0); v.ij.add(new Integer[] {0, 0}); S.put(a, v); } else { Values v = S.get(a); int ai, aj; if (v.di.containsKey(i)) { ai = v.di.get(i); } else { ai = v.di.size(); v.di.put(i, ai); } if (v.dj.containsKey(j)) { aj = v.dj.get(j); } else { aj = v.dj.size(); v.dj.put(j, aj); } v.ij.add(new Integer[] {ai, aj}); } } } } scan.close(); int cnt = 0; for (Values v : S.values()) { int h = v.di.size(); int w = v.dj.size(); V = h + w; G = new ArrayList>(); for (int i=0; i < V; i++) { G.add(new ArrayList()); } for (Integer[] i : v.ij) { add_edge(i[0], i[1]+h); } int n = mpc(h, w); cnt += n; } System.out.println(cnt); } }