BZOJ 2466: [中山市选2009]树( 高斯消元 )

时间：2021-05-27 19:32:35

BZOJ 2466: [中山市选2009]树( 高斯消元 )

高斯消元解异或方程组...然后对*元进行暴搜。树形dp应该也是可以的...

--------------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
 
using namespace std;
 
const int maxn = 109;
 
bitset<maxn> mat[maxn];
int N, State[maxn], Id[maxn], ans;
 
void Init() {
for(int i = 0; i < N; i++) {
mat[i].reset();
mat[i][i] = mat[i][N] = 1;
}
for(int i = 1; i < N; i++) {
int u, v;
scanf("%d%d", &u, &v); u--; v--;
mat[u][v] = mat[v][u] = 1;
}
ans = maxn;
memset(Id, -1, sizeof Id);
}
 
void Work() {
int k = 0;
for(int i = 0; i < N; i++) {
for(int j = k; j < N; j++) if(mat[j][i]) {
if(j != k)
swap(mat[j], mat[k]);
break;
}
if(mat[k][i]) {
for(int j = k; ++j < N; ) if(mat[j][i])
mat[j] ^= mat[k];
Id[i] = k++;
}
}
}
 
void Dfs(int x, int sum) {
if(sum >= ans)
return;
if(x < 0) {
ans = sum; return;
}
if(~Id[x]) {
State[x] = mat[Id[x]][N];
for(int i = x; ++i < N; )
if(mat[Id[x]][i]) State[x] ^= State[i];
Dfs(x - 1, sum + State[x]);
} else {
State[x] = 0; Dfs(x - 1, sum);
State[x] = 1; Dfs(x - 1, sum + 1);
}
}
 
int main() {
while(scanf("%d", &N) == 1 && N) {
Init();
Work();
Dfs(N - 1, 0);
printf("%d\n", ans);
}
return 0;
}

--------------------------------------------------------------------------------------

2466: [中山市选2009]树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 561  Solved: 226
[Submit][Status][Discuss]

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 <= n <=100。

Source

相关文章