SRM 527 DIV1 450 P8XMatrixRecovery

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

view plainprint?

1. int r;  
2. int c;  
3. bool edge[60][60];  
4. bool used[60];  
5. int pr[60];  
6.   
7. class P8XMatrixRecovery {  
8.     bool dfs(int s) {  
9.         used[s] = 1;  
10.   
11.         REP(v, 2*c) {  
12.             if (!edge[s][v])  
13.                 continue;  
14.             int w = pr[v];  
15.             if (w == -1 || (!used[w] && dfs(w))) {  
16.                 pr[s] = v;  
17.                 pr[v] = s;  
18.                 return true;  
19.             }  
20.         }  
21.         return false;  
22.     }  
23.   
24.     int match(vector<string> &rows, vector<string> &cols) {  
25.         memset(edge, 0, sizeof(edge));  
26.         REP(i, c) REP(j, c) {  
27.             edge[i][j+c] = edge[j+c][i] = 1;  
28.             REP(k, r) {  
29.                 if (cols[j][k] != '?' && rows[k][i] != '?' && rows[k][i] != cols[j][k]) {  
30.                     edge[i][j+c] = edge[j+c][i] = 0;  
31.                     break;  
32.                 }  
33.             }  
34.         }  
35.   
36.         int ret = 0;  
37.         memset(pr, -1, sizeof(pr));  
38.         REP(i, 2*c) {  
39.             if (pr[i] >= 0)  
40.                 continue;  
41.             memset(used, 0, sizeof(used));  
42.             if (dfs(i))  
43.                 ++ret;  
44.         }  
45.   
46.         return ret;  
47.     }  
48.   
49. public:  
50.     vector<string> solve(vector<string> rows, vector<string> columns) {  
51.         r = rows.size();  
52.         c = rows[0].length();  
53.   
54.         REP(i, r) REP(j, c) {  
55.             if (rows[i][j] == '?') {  
56.                 rows[i][j] = '0';  
57.   
58.                 if (match(rows, columns) < c)  
59.                     rows[i][j] = '1';  
60.             }  
61.         }  
62.   
63.         return rows;  
64.     }  
65. };  

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;
    }
};