SRM527 Div1 Medium

450

辞書順最小は先頭から決める。
1つ以上の答えがあるそうなので、順に0を割り当てて試す。
ある場所に0を割り当ててマトリックスを作れないのならば、そこに1を入れればいい。
マトリックスになるかどうかは、2部マッチングをすればよい。

struct E {
  int src, dst;
  E (int s, int d) : src(s), dst(d) {}
};

const int N = 30 * 2 + 5;
vector<E> g[N];

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

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

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

int make_graph(vector<string> R, vector<string> C)
{
  fill(g, g + N, vector<E>());

  const int H = R.size();
  const int W = C.size();

  for (int i = 0; i < W; ++i) {
    for (int j = 0; j < W; ++j) {
      bool flg = true;
      for (int k = 0; k < H; ++k) {
        if (R[k][i] == '?') continue;
        if (C[j][k] == '?') continue;
        flg = flg && (R[k][i] == C[j][k]);
      }
      if (flg) add_edge(i, j + W);
    }
  }

  return W + W;
}

int matching(vector<string> R, vector<string> C)
{
  const int V = make_graph(R, C);

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

class P8XMatrixRecovery {
public:
  vector <string> solve(vector <string> R, vector <string> C)
  {
    const int H = R.size();
    const int W = C.size();

    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (R[i][j] == '?') {
          R[i][j] = '0';
          if (matching(R, C) != W) R[i][j] = '1';
        }
      }
    }

    return R;
  }
};