记录编号	38322	评测结果	AAAAAAAAAAAAAAAAA
题目名称	牛棚的灯	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2012-04-17 11:46:33	内存使用	0.27 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 40, INF = ~0u>>2;
int n, m, x, y, a = INF, G[N][N];
bool b[N], s[N];
void Swap(int i, int j) {
    for(int l=1; l<=n; l++)
        swap(G[i][l], G[j][l]);
    swap(b[i], b[j]);
}
void Xor(int i, int j) {
    for(int l=1; l<=n; l++)
        G[i][l] ^= G[j][l];
    b[i] ^= b[j];
}
void DFS(int k, int c) {
    if(c >= a) return;
    if(k == 0) {
        if(c < a) a = c;
        return;
    }
    if(G[k][k]) {
        bool t = b[k];
        for(int i=k+1; i<=n; i++) if(G[k][i])
            t ^= s[i];
        (s[k] = t) ? DFS(k-1, c+1) : DFS(k-1, c);
    } else {
        s[k] = false; DFS(k-1, c);
        s[k] = true; DFS(k-1, c+1);
        s[k] = false;
    }
}
int main() {
    freopen("lights.in", "r", stdin);
    freopen("lights.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++) G[i][i] = b[i] = 1;
    for(int i=1; i<=m; i++) {
        scanf("%d %d", &x, &y);
        G[x][y] = G[y][x] = 1;
    }
    for(int k=1; k<=n; k++) {
        bool f = false;
        for(int i=k; i<=n; i++) if(G[i][k]) {
            f = true;
            Swap(i, k);
            break;
        }
        if(!f) continue;
        for(int i=k+1; i<=n; i++) if(G[i][k])
            Xor(i, k);
    }
    DFS(n, 0);
    printf("%d\n", a);
    return 0;
}