BZOJ2466【中山市选2009】树 <高斯消元>

Problem

【中山市选2009】树

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

图论中的树为一个无环的无向图。给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的），并且该节点的直接邻居也发生同样的变化。开始的时候，所有的指示灯都是熄灭的。
请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。

Input

输入文件有多组数据。
输入第一行包含一个整数$n$，表示树的节点数目。每个节点的编号从$1$到$n$。
输入接下来的$n–1$行，每一行包含两个整数$x$，$y$，表示节点$x$和$y$之间有一条无向边。
当输入$n$为$0$时，表示输入结束。

Output

对于每组数据，输出最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。

Sample Input

3
1 2
1 3
0

Sample Output

1

HINT

对于$100\%$的数据，满足$1\le n\le100$。

标签：高斯消元

Solution

将所有节点按的次数设为$x_1\sim x_n$，会得到一个线性异或方程组。
这时可以$bitset+高消$水过。

不懂高消可以戳这里。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#define MAX_N 100
using namespace std;
int n, x[MAX_N+5], num[MAX_N+5], cnt;
bitset <MAX_N+5> f[MAX_N+5];
void init() {cnt = 0;    for (int i = 1; i <= n; i++)	f[i].reset(), f[i][i] = f[i][n+1] = 1;}
void gauss() {
    int cur = 1;
    for (int i = 1, tmp; i <= n; i++) {
        for (tmp = cur; tmp <= n; tmp++)	if (f[tmp][i] == 1)	break;
        if (tmp > n) {num[cnt++] = i;	continue;}	swap(f[cur], f[tmp]);
        for (int j = 1; j <= n; j++)	if (j != cur && f[j][i])	f[j] ^= f[cur];
        cur++;
    }
}
int calc(int sta) {
    int ret = 0;
    for (int i = 1; i <= n; i++)	x[i] = f[i][n+1];
    for (int i = 0; i < cnt; i++) {
        if (!(sta&(1<<i)))	continue;	ret++;
        for (int j = 1; j <= n; j++)	if (f[j][num[i]])	x[j] ^= 1;
    }
    for (int i = 1; i <= n; i++)	ret += x[i];
    return ret;
}
int main() {
    while (scanf("%d", &n) && n != 0) {
        init();
        for (int i = 1, u, v; i < n; i++)	scanf("%d%d", &u, &v), f[u][v] = f[v][u] = 1;
        gauss();	int ans = n;
        for (int sta = 0; sta < (1<<cnt); sta++)	ans = min(ans, calc(sta));
        printf("%d\n", ans);
    }
    return 0;
}