[bzoj2466]:[中山市选2009]树

[bzoj2466]:[中山市选2009]树

Description

给定一棵树,每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了,那么该节点的灯会从熄灭变为点亮(当按之前是熄灭的),或者从点亮到熄灭(当按之前是点亮的)。并且该节点的直接邻居也发生同样的变化。

开始的时候,所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。


Hint

$n \leq 100$


Solution

显然一个灯最多只会被摁一次,多余的是没有意义的。。

解法一 考虑dp

设g表示不摁下这盏灯,f表示摁下,0/1分别表示灯不亮,亮,以u为节点的且其子树都亮的最小代价。

答案就是min(g[1][1],f[1][1])

考虑转移 因为如果摁下这盏灯其子树都亮的条件是 其儿子节点都不亮,所以 f 一定都是从0转移过来的 g一定都是从1转移过来的。
二亮与不亮需要考虑奇偶性。然后dp的式子就好理解了嘛。

复杂度$O(n)$

解法二 考虑高斯消元

考虑问题的本质,实际上是给定一组异或方程,求得一组解使得$\sum$ 系数最小

高斯消元以后,爆搜自由元,$2^s$ 枚举即可

复杂度$O(n^3+2^s)$


Code

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

using namespace std;

inline int read() {
    char c = getchar(); int x = 0;
    while(!isdigit(c)) c = getchar();
    do {
        x = x * 10 + (c ^ 48);
        c = getchar();
    } while(isdigit(c));
    return x;
}

const int N = 105;
int head[N];
struct E {
    int nxt, to;
}edg[N << 1];
int g[N][2], f[N][2];
int n, cnt;

void dfs(int u, int father) {
    g[u][1] = f[u][0] = n + 1;
    g[u][0] = 0; f[u][1] = 1;
    for(int i = head[u]; ~i; i = edg[i].nxt) {
        int v = edg[i].to;
        if(v == father) continue;
        dfs(v, u);
        int f0 = f[u][0], f1 = f[u][1];
        int g0 = g[u][0], g1 = g[u][1];
        g[u][0] = min(g1 + f[v][1], g0 + g[v][1]);
        g[u][1] = min(g1 + g[v][1], g0 + f[v][1]);
        f[u][0] = min(f1 + f[v][0], f0 + g[v][0]);
        f[u][1] = min(f0 + f[v][0], f1 + g[v][0]);
    }
}

void add(int from, int to) {
    edg[++cnt] = (E) {head[from], to};
    head[from] = cnt;
}

int main() {
    n = read();
    while(n) {
        memset(head, -1, sizeof(head));
        cnt = 0;
        for(int i = 1; i < n; ++i) {
            register int ta = read(), tb = read();
            add(ta, tb); add(tb, ta);
        }
        dfs(1, 0);
        printf("%d\n", min(f[1][1], g[1][1]));
        n = read();
    }
    return 0;
}

and

#include<cstdio>
#include<cmath>
#include<cctype>
#include<bitset>
#include<algorithm>
#include<cstring>

using namespace std;

inline int read() {
    char c = getchar(); int x = 0;
    while(!isdigit(c)) c = getchar();
    do {
        x = x * 10 + (c ^ 48);
        c = getchar();
    } while(isdigit(c));
    return x;
}

const int N = 105;
int head[N], x[N], pivot[N], qwq[N], val[N];
struct E {
    int nxt, to;
}edg[N << 1];
int n, ans, cnt, cur;
bitset<N> a[N];

void add(int from, int to) {
    edg[++cnt] = (E) {head[from], to};
    head[from] = cnt;
}

void ghost() {
    cur = 1;
    for(int i = 1; i <= n; ++i) {
        int j = cur;
        for(; j <= n; ++j)
            if(a[j][i]) break;
        if(j == n + 1) {
            qwq[++qwq[0]] = i; 
            continue;
        }
        if(j != cur)
            swap(a[cur], a[j]);
        for(int k = 1; k <= n; ++k) 
            if(a[k][i] && k != cur) 
                a[k] ^= a[cur]; 
        pivot[i] = cur;
        cur++;
    }
    cur--;
}

void dfs(int d, int tot) {
    if(d == 0) {
        ans = min(ans, tot);
        return;
    }
    if(tot >= ans) return;
    if(pivot[d]) {
        bitset<N> &t = a[pivot[d]];
        int x = t[n + 1];
        for(int i = 1; i <= qwq[0]; ++i)
            if(t[qwq[i]]) x ^= val[qwq[i]]; 
        dfs(d - 1, tot + x);
    } else {
        val[d] = 0; dfs(d - 1, tot);
        val[d] = 1; dfs(d - 1, tot + 1);
    }
}

int main() {
    n = read();
    while(n) {
        for(int i = 1; i <= n; ++i) a[i].reset();
        memset(pivot, 0, sizeof(pivot));
        memset(qwq, 0, sizeof(qwq));
        cnt = 0; ans = n;
        for(int i = 1; i < n; ++i) {
            register int ta = read(), tb = read();
            a[ta][tb] = 1; a[tb][ta] = 1;
        }
        for(int i = 1; i <= n; ++i) {
            a[i][i] = 1; a[i][n + 1] = 1;
        }
        ghost();
        dfs(n, 0);
        printf("%d\n", ans);
        n = read();
    }
    return 0;
}

说点什么

avatar
  Subscribe  
提醒