// code template is in https://github.com/drken1215/algorithm/blob/master/template_minimum.cpp #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; //------------------------------// // Utility //------------------------------// using ll = long long; using i128 = __int128_t; using u128 = __uint128_t; using pint = pair; using pll = pair; using tll = array; using fll = array; using vint = vector; using vll = vector; using dint = deque; using dll = deque; using vvint = vector>; using vvll = vector>; using vpll = vector>; template using min_priority_queue = priority_queue, greater>; template inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); } template inline auto maxll(S a, T b) { return max(ll(a), ll(b)); } template inline auto minll(S a, T b) { return min(ll(a), ll(b)); } template auto max(const T &a) { return *max_element(a.begin(), a.end()); } template auto min(const T &a) { return *min_element(a.begin(), a.end()); } template auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); } template auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); } template auto accum(const vector &a) { return accumulate(a.begin(), a.end(), T()); } template auto accum(const deque &a) { return accumulate(a.begin(), a.end(), T()); } #define REP(i, a) for (long long i = 0; i < (long long)(a); i++) #define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++) #define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i) #define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i) #define EB emplace_back #define PF push_front #define PB push_back #define MP make_pair #define FI first #define SE second #define ALL(x) x.begin(), x.end() #define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl // input template istream& operator >> (istream &is, vector &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } template istream& operator >> (istream &is, deque &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } template istream& operator >> (istream &is, vector> &P) { for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; } // output template ostream& operator << (ostream &s, const pair &P) { return s << '<' << P.first << ", " << P.second << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; } template ostream& operator << (ostream &s, const array &P) { return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; } template ostream& operator << (ostream &s, const vector &P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, const deque &P) { for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; } template ostream& operator << (ostream &s, const vector> &P) { for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; } template ostream& operator << (ostream &s, const set &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const multiset &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const unordered_set &P) { for (auto it : P) { s << "<" << it << "> "; } return s; } template ostream& operator << (ostream &s, const map &P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } template ostream& operator << (ostream &s, const unordered_map &P) { for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; } void yes(bool a) { cout << (a ? "yes" : "no") << endl; } void YES(bool a) { cout << (a ? "YES" : "NO") << endl; } void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; } const vector DX = {1, 0, -1, 0, 1, -1, 1, -1}; const vector DY = {0, 1, 0, -1, 1, -1, -1, 1}; // Hopcroft-Karp struct HopcroftKarp { const int NOT_MATCHED = -1; // input int size_left, size_right; vector> list; // left to right vector> rlist; // right to left // results vector lr, rl; // intermediate results vector seen, matched; vector level; // constructor HopcroftKarp(int L, int R) : size_left(L), size_right(R), list(L), rlist(R) {} void add_edge(int from, int to) { assert(from >= 0 && from < size_left); assert(to >= 0 && to < size_right); list[from].emplace_back(to); rlist[to].emplace_back(from); } // getter, debugger const vector &operator [] (int i) const { return list[i]; } friend ostream& operator << (ostream& s, const HopcroftKarp& G) { s << endl; for (int i = 0; i < (int)G.list.size(); ++i) { s << i << ": "; for (int j = 0; j < (int)G.list[i].size(); ++j) { s << G.list[i][j]; if (j + 1 != (int)G.list[i].size()) s << ", "; } s << endl; } return s; } // solver void hobfs() { queue que; for (int left = 0; left < size_left; ++left) { level[left] = -1; if (!matched[left]) { que.push(left); level[left] = 0; } } level[size_left] = size_left; while (!que.empty()) { int left = que.front(); que.pop(); for (int right : list[left]) { int next = rl[right]; if (next == NOT_MATCHED) next = size_left; if (level[next] == -1) { level[next] = level[left] + 1; que.push(next); } } } } bool hodfs(int left) { if (left == size_left) return true; if (seen[left]) return false; seen[left] = true; for (int right : list[left]) { int next = rl[right]; if (next == NOT_MATCHED) next = size_left; if (level[next] > level[left] && hodfs(next)) { lr[left] = right; rl[right] = left; return true; } } return false; } int solve() { seen.assign(size_left, false); matched.assign(size_left, false); level.assign(size_left + 1, -1); lr.assign(size_left, -1); rl.assign(size_right, -1); int res = 0; while (true) { hobfs(); seen.assign(size_left, false); bool finished = true; for (int left = 0; left < size_left; ++left) { if (!matched[left] && hodfs(left)) { matched[left] = true; ++res; finished = false; } } if (finished) break; } for (int r = 0; r < size_right; r++) { if (rl[r] != NOT_MATCHED) lr[rl[r]] = r; } return res; } // various construction // max matching vector> get_matching() { vector> res; for (int v = 0; v < size_left; v++) { if (lr[v] == NOT_MATCHED) continue; res.emplace_back(v, lr[v]); } return res; } // enumerate reachable nodes (0: left, 1: right) const int LEFT = 0, RIGHT = 1; pair, vector> get_reachable() { vector can_left(size_left, false); vector can_right(size_right, false); queue> que; for (int v = 0; v < size_left; v++) { if (lr[v] == NOT_MATCHED) { can_left[v] = true; que.push({LEFT, v}); } } while (!que.empty()) { auto [which, v] = que.front(); que.pop(); if (which == LEFT) { for (auto r : list[v]) { if (!can_right[r]) { can_right[r] = true; que.push({RIGHT, r}); } } } else { int l = rl[v]; if (l != NOT_MATCHED && !can_left[l]) { can_left[l] = true; que.push({LEFT, l}); } } } return {can_left, can_right}; } // max independent set (0: left, 1: right) vector> get_independent_set() { vector> res; auto [can_left, can_right] = get_reachable(); for (int v = 0; v < size_left; v++) { if (can_left[v]) res.emplace_back(LEFT, v); } for (int v = 0; v < size_right; v++) { if (!can_right[v]) res.emplace_back(RIGHT, v); } return res; } // min vertex-cover (0: left, 1: right) vector> get_vertex_cover() { vector> res; auto [can_left, can_right] = get_reachable(); for (int v = 0; v < size_left; v++) { if (!can_left[v]) res.emplace_back(LEFT, v); } for (int v = 0; v < size_right; v++) { if (can_right[v]) res.emplace_back(RIGHT, v); } return res; } // min edge-cover (0: left, 1: right) vector> get_edge_cover() { vector> res = get_matching(); for (int v = 0; v < size_left; v++) { if (list[v].empty()) return vector>(); // infeasible if (lr[v] == NOT_MATCHED) res.emplace_back(v, list[v][0]); } for (int v = 0; v < size_right; v++) { if (rlist[v].empty()) return vector>(); // infeasible if (rl[v] == NOT_MATCHED) res.emplace_back(rlist[v][0], v); } return res; } }; //------------------------------// // Solver //------------------------------// int main() { ll H, W; cin >> H >> W; vvll A(H, vll(W)); cin >> A; unordered_set S; REP(i, H) REP(j, W) S.insert(A[i][j]); ll res = 0; for (auto val : S) { if (val == 0) continue; HopcroftKarp hk(H, W); REP(i, H) REP(j, W) if (A[i][j] == val) hk.add_edge(i, j); hk.solve(); auto cover = hk.get_vertex_cover(); res += cover.size(); } cout << res << endl; }