BZOJ 1770 - [Usaco2009 Nov]lights 灯

Published on 2016-12-04

题目地址

描述

贝希和她的闺密们在她们的牛棚中玩游戏。但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏!

牛棚中一共有 n(1n35)n(1 \le n \le 35) 盏灯,编号为 11nn。这些灯被置于一个非常复杂的网络之中。有 m(1m595)m(1\le m\le 595) 条很神奇的无向边,每条边连接两盏灯。每盏灯上面都带有一个开关。当按下某一盏灯的开关的时候,这盏灯本身,还有所有有边连向这盏灯的灯的状态都会被改变。状态改变指的是:当一盏灯是开着的时候,这盏灯被关掉;当一盏灯是关着的时候,这盏灯被打开。问最少要按下多少个开关,才能把所有的灯都给重新打开。

数据保证至少有一种按开关的方案,使得所有的灯都被重新打开。

分析

对高斯消元理解不深刻导致做题产生问题qwq。

根据题目,每盏灯要么按要么不按,设 xix_i 为是否按 ii 处的灯,根据连边情况,我们可以列出一个 nn 个未知数,nn 个不等式的异或方程。由于题目保证有解,而无解的原因是有矛盾方程,因为对矩阵做任意的初等行变换都不影响方程的解,所以无需担心无解的情况(也就是说怎么消元行,不管无解的情况)。

接着我们考虑来解这个方程,当解到某个变量时,没有发现有系数非 00 的变量,也就意味着这个变量不可解,它是自由变量,我们应该跳过这一行,处理下一个变量。到最后,ai,i=0a_{i, i} = 0 的变量 xix_i 就是自由变量。而且可以证明,「跳过这一行」这一举动并不影响最终自由变量的个数。

一旦确定了自由变量的值,整个方程的解也就明确了。由于现在的矩阵是一个上三角矩阵(对角线下方必然为 00),我们考虑倒序DFS 每一个变量 ii,如果它不是自由变量,那么就计算它的值,否则我们枚举 xi=0x_i = 0xi=1x_i = 1 两种情况,枚举完后更新答案即可。注意加上最优性剪枝。

由于自由变量的个数不明确,所以复杂度也不明确,权当复习高斯消元了。

另外一种做法,考虑折半搜索。预处理出前 n2\lfloor \frac n 2\rfloor 个按钮的开关情况下,灯的状态(压在 long long 中,00 表示关,11 表示开),将其存入数组,然后排序。然后枚举后 n2\lceil \frac n 2\rceil 个按钮的开关情况下,灯的状态 ss,在数组中二分查找是否存在 (2n1)s(2^n - 1)\oplus s 这个数即可。

复杂度:O(2n2log2n2)=O(n2n2)O(2^{\frac n 2}\log 2^{\frac n 2}) = O(n\cdot 2^{\frac n 2})

代码

//  Created by Sengxian on 2016/12/02.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1770 高斯消元or折半搜索
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 35 + 3;
int n, m, ans = MAX_N, now = 0;
bool G[MAX_N][MAX_N], a[MAX_N][MAX_N], caled[MAX_N], val[MAX_N];

void gaussJordan(int n, bool a[][MAX_N]) {
    for (int i = 0; i < n; ++i) {
        int idx = -1;
        for (int j = i; j < n; ++j) if (a[j][i]) {
            idx = j;
            break;
        }

        if (idx == -1) continue;
        if (idx != i) for (int j = i; j <= n; ++j) swap(a[i][j], a[idx][j]);

        for (int j = 0; j < n; ++j) if (j != i && a[j][i])
            for (int k = i; k <= n; ++k) a[j][k] ^= a[i][k];
    }
}

bool s[MAX_N];

inline bool judge() {
    for (int i = 0; i < n; ++i)
        if (!s[i]) return false;
    return true;
}

void dfs(int i) {
    if (now >= ans) return;
    if (i == -1) {
        ans = min(ans, now);
        return;
    }

    if (a[i][i]) {
        int v = a[i][n];
        for (int j = i + 1; j < n; ++j) if (a[i][j]) v ^= val[j];
        now += v;
        dfs(i - 1);
        now -= v;
    } else {
        // not choose
        dfs(i - 1);

        // choose
        now++, val[i] = true;
        dfs(i - 1);
        now--, val[i] = false;
    }
}


int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = readInt(), m = readInt();
    for (int i = 0, u, v; i < m; ++i) {
        u = n - readInt(), v = n - readInt();
        a[u][v] = a[v][u] = true;
        G[u][v] = G[v][u] = true;
    }

    for (int i = 0; i < n; ++i) a[i][i] = a[i][n] = 1, G[i][i] = true;

    gaussJordan(n, a);
#ifdef DEBUG
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= n; ++j)
            cout << a[i][j] << ' ';
        cout << endl;
    }
#endif

    dfs(n - 1);

    printf("%d\n", ans);
    return 0;
}