记录编号	314513	评测结果	AAAAAAAAAA
题目名称	染色	最终得分	100
用户昵称	Ezoi_Vermouth	是否通过	通过
代码语言	C++	运行时间	1.879 s
提交时间	2016-10-03 16:45:08	内存使用	1.54 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int kN = 18;

int f[1 << kN];
bool is_ok[1 << kN];
int N, g[kN];

unsigned power(unsigned d, unsigned k) {
    if (!k) return 1;
    unsigned tmp = power(d, k / 2);
    tmp = tmp * tmp;
    if (k % 2) tmp = tmp * d;
    return tmp;
}

void work() {
    scanf("%d", &N);
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(is_ok, 0, sizeof(is_ok));
    
    for (int i = 0; i < N; i++) {
        char tmp[20]; scanf("%s", &tmp);
        for (int j = 0; j < N; j++) {
            if (tmp[j] == '1') g[i] |= 1 << j;
        }
    }
    
    unsigned int ans = 0;
    
    for (int ss = 1; ss < (1 << N); ss++) {
        bool ok = true;
        for (int i = 0; i < N; i++) if (ss & (1 << i)) {
            if (ss & g[i]) {
                ok = false;
                break;
            }
        }
        is_ok[ss] = ok;
    }
    
    for (int s = 1; s < (1 << N); s++) {
        int tmp = 10000;
        for (int ss = s; ss > 0; ss = (ss - 1) & s) {
            if (is_ok[ss]) {
                tmp = min(tmp, 1 + f[s ^ ss]);
            }
        }
        f[s] = tmp;
        // printf("f[%d] = %d\n", s, tmp);
        ans += (unsigned) tmp * power(233, s);
    }
    
    printf("%u\n", ans);
}

int main() {
    freopen("ezcolor.in", "r", stdin);
    freopen("ezcolor.out", "w", stdout);
    int t=1;
    //scanf("%d", &t);
    while (t--) {
        work();
    }
    fclose(stdout); 
    return 0;
}