BZOJ 1770 - [Usaco2009 Nov]lights 灯

#数学 #高斯消元 #折半搜索
Published on 2016-12-04

题目地址

描述

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

牛棚中一共有 n(1≤n≤35)n(1 \le n \le 35) 盏灯，编号为 11 到 nn。这些灯被置于一个非常复杂的网络之中。有 m(1≤m≤595)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 = 0 或 xi=1x_i = 1 两种情况，枚举完后更新答案即可。注意加上最优性剪枝。

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

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

复杂度：O(2n2log2n2)=O(n⋅2n2)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;
}
Codeforces 735E - Ostap and Tree