Search on the blog

2011年12月20日火曜日

SRM 527 DIV1 450 P8XMatrixRecovery

2部グラフのマッチングまでは、気付いてた。あと一歩だった。
"ある条件を満たす辞書順最小のものを求めよ。"という問題はgreedyで解ける場合が多いような気がする。
int r;
int c;
bool edge[60][60];
bool used[60];
int pr[60];

class P8XMatrixRecovery {
bool dfs(int s) {
used[s] = 1;

REP(v, 2*c) {
if (!edge[s][v])
continue;
int w = pr[v];
if (w == -1 || (!used[w] && dfs(w))) {
pr[s] = v;
pr[v] = s;
return true;
}
}
return false;
}

int match(vector<string> &rows, vector<string> &cols) {
memset(edge, 0, sizeof(edge));
REP(i, c) REP(j, c) {
edge[i][j+c] = edge[j+c][i] = 1;
REP(k, r) {
if (cols[j][k] != '?' && rows[k][i] != '?' && rows[k][i] != cols[j][k]) {
edge[i][j+c] = edge[j+c][i] = 0;
break;
}
}
}

int ret = 0;
memset(pr, -1, sizeof(pr));
REP(i, 2*c) {
if (pr[i] >= 0)
continue;
memset(used, 0, sizeof(used));
if (dfs(i))
++ret;
}

return ret;
}

public:
vector<string> solve(vector<string> rows, vector<string> columns) {
r = rows.size();
c = rows[0].length();

REP(i, r) REP(j, c) {
if (rows[i][j] == '?') {
rows[i][j] = '0';

if (match(rows, columns) < c)
rows[i][j] = '1';
}
}

return rows;
}
};

0 件のコメント:

コメントを投稿