SRM557 Div1 Medium

550
DAGの最小パス被覆。Dilworthの定理。
サイクルに含まれるような頂点は無視する。

const int N = 100 + 5;
vector<int> g[N];
bool h[N][N];

int match[N];
bool vis[N];

void add_edge(int src, int dst)
{
  dst += 50;
  g[src].push_back(dst);
  g[dst].push_back(src);
  return ;
}

bool rec(int v)
{
  vis[v] = true;
  for (int i = 0; i < g[v].size(); ++i) {
    int u = g[v][i];
    int w = match[u];
    if (w < 0 || !vis[w] && rec(w)) {
      match[v] = u;
      match[u] = v;
      return true;
    }
  }
  return false;
}

int matching(void)
{
  fill(match, match + N, -1);
  int ret = 0;
  for (int i = 0; i < N; ++i) {
    if (match[i] == -1) {
      fill(vis, vis + N, false);
      if (rec(i)) ++ret;
    }
  }
  return ret;
}

class Incubator {
public:
  int maxMagicalGirls(vector <string> love)
  {
    const int M = love.size();

    for (int i = 0; i < M; ++i) {
      for (int j = 0; j < M; ++j) {
        h[i][j] = (love[i][j] == 'Y');
      }
    }

    for (int k = 0; k < N; ++k) {
      for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
          h[i][j] = h[i][j] || (h[i][k] && h[k][j]);
        }
      }
    }

    int cyc = 0;
    for (int i = 0; i < N; ++i) {
      cyc += h[i][i];
    }

    fill(g, g + N, vector<int>());
    for (int i = 0; i < M; ++i) {
      for (int j = 0; j < M; ++j) {
        if (h[i][j] && !h[i][i] && !h[j][j]) {
          add_edge(i, j);
        }
      }
    }

    return max(0, M - matching() - cyc);
};