---

目录

• [TOC]

题目链接

luogu P2962 [USACO09NOV]灯Lights

题解

可以折半搜索

map合并

复杂度

2^(n / 2)*logn

高斯消元后得到每个点的翻转状态

爆搜*元得到最优翻转状态

// luogu-judger-enable-o2

#include<map>

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define gc getchar()

#define pc putchar

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9') c = getchar();

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

    return x * f;

}

void print(int x) {

    if(x < 0) {

        putchar('-');

        x = -x;

    }

    if(x >= 10) print(x / 10);

    putchar(x % 10 + '0');

}

#define LL long long

int n,m;

LL s[200];

int cnt,ans = 0x3f3f3f3f;

std::map<LL,int>b;

LL ed;

bool flag;

void dfs(int x,LL now,int used) {

    if(x == cnt + 1) {

        if(now == ed) ans = std::min(used,ans);

        if(!flag) {

            int t = b[now];

            if(!t || t > used) b[now] = used;

        } else {

            int t = b[ed ^ now] ;

            if(!t) return ;

            ans = std::min(ans,t + used);

        }

        return ;

    }

    dfs(x + 1,now,used);

    dfs(x + 1,now ^ s[x],used + 1);

}

int main() {

    //freopen("data.cpp","r",stdin);

    n = read(), m = read();

    for(int i = 1;i <= m;++ i) {

        int u = read(),v = read();

        s[u] |= (1ll << v - 1) ,s[v] |= (1ll << u - 1);

    }

    ed = (1ll << n) - 1;

    //print(ed); pc('\n');

    for(int i = 1;i <= n;++ i) s[i] |= (1ll << i - 1);

    cnt = n / 2;

    dfs(1,0,0);

    flag = 1; cnt = n;

    dfs(n / 2 + 1,0,0);

    print(ans);

    pc('\n');

}

#include<map>

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define rep(a,b,c) for(int a = b; a <= c;++ a)

#define per(a,b,c) for(int a = b; a >= c; -- a)

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = getchar();

	while(c < '0' || c > '9') c = getchar();

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

	return x * f;

}

void print(int x) {

	if(x < 0) {

		putchar('-');

		x = -x;

	}

	if(x >= 10) print(x / 10);

	putchar(x % 10 + '0');

}

#define LL long long

int n,m;

const int maxn = 37;

int f[maxn][maxn];

bool flag;

void guass() {

	rep(i,1,n) {

		int j = i;

		while(!f[j][i] && j <= n) ++ j;

		if(j == n + 1) continue;

		if(i != j) swap(f[i],f[j]);

		rep(j,1,n)

			if(j != i && f[j][i])

				rep(k,1,n + 1)

					f[j][k] ^= f[i][k];

	}

}

int zy[maxn],tot = 0,ans = 0x3f3f3f3f;

void dfs(int now) {

	if(tot > ans) return;

	if(!now) {

		ans = std::min(ans,tot);

		return ;

	}

	if(f[now][now]) {

		int t = f[now][n + 1];

		rep(i,now + 1,n) if(f[now][i]) t ^= zy[i];

		zy[now] = t;

		if(t) tot ++;

		dfs(now - 1);

		if(t) tot --;

	} else {

		zy[now] = 0;

		dfs(now - 1);

		zy[now] = 1;

		tot ++;

		dfs(now - 1);

		tot --;

	}

}

int main() {

	n = read(),m = read();

	rep(i,1,n) f[i][i] = f[i][n + 1] = 1;

	rep(i,1,m) {

		int x = read(),y = read();

		f[x][y] = f[y][x] = 1;

	}

	guass();

	dfs(n);

	print(ans);

	pc('\n');

}