(二分图匹配，匈牙利算法)LCP 04. 覆盖

LCP 04. 覆盖

匈牙利算法

棋盘格子可以划分为二分图

只能是圈和叉的格子（相邻的格子）建立边，自然就分成了圈和叉两部分点集

const int N = 1000;

int e[N], ne[N], h[N], idx, match[N];
bool st[N];

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

class Solution {
 public:
  void init() {
    memset(h, -1, sizeof h);
    memset(e, 0, sizeof e);
    memset(ne, 0, sizeof ne);
    memset(match, 0, sizeof match);
    idx = 0;
  }

  bool find(int x) {
    for (int i = h[x]; ~i; i = ne[i]) {
      int j = e[i];
      if (!st[j]) {
        st[j] = true;
        if (match[j] == 0 || find(match[j])) {
          match[j] = x;
          return true;
        }
      }
    }
    return false;
  }

  int domino(int n, int m, vector<vector<int>>& broken) {
    init();
    int g[n + 1][m + 1];
    memset(g, 0, sizeof g);
    int k = 1;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++) g[i][j] = k++;
    for (auto p : broken) g[p[0] + 1][p[1] + 1] = -1;

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (g[i][j] == -1) continue;
        if (j + 1 <= m && g[i][j + 1] != -1)
          add(g[i][j], g[i][j + 1]), add(g[i][j + 1], g[i][j]);
        if (i + 1 <= n && g[i + 1][j] != -1)
          add(g[i][j], g[i + 1][j]), add(g[i + 1][j], g[i][j]);
      }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = i & 1 ? 1 : 2; j <= m; j += 2) {
        if (g[i][j] == -1) continue;
        memset(st, 0, sizeof st);
        if (find(g[i][j])) res++;
      }
    }
    return res;
  }
};