bzoj2466: [中山市选2009]树

同上一题。（应该可以树形dp，然而我不会。。。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<bitset>

#include<algorithm>

using namespace std;

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

#define clr(x,c) memset(x,c,sizeof(x))

int read(){

	int x=0;char c=getchar();

	while(!isdigit(c)) c=getchar();

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x;

}

const int nmax=105;

const int inf=0x7f7f7f7f;

bitset<nmax>a[nmax];

int ans[nmax],res=inf,tot=0,N;

void Gauss(int n,int m){

	REP(i,1,n){

		int j;

		for(j=i;j<=n&&!a[j][i];j++)

		if(j>n) continue;

		if(j!=i) swap(a[i],a[j]);

		REP(j,i+1,n) if(a[j][i]) a[j]^=a[i];

	}

}

void dfs(int x){

	if(tot>=res) return ;

	if(!x){

		res=min(res,tot);return ;

	}

	if(a[x][x]){

		int t=a[x][N+1];

		REP(i,x+1,N) if(a[x][i]) t^=ans[i];

		ans[x]=t;

		if(t) tot++;

		dfs(x-1);

		if(t) tot--;

	}else{

		ans[x]=0;dfs(x-1);

		ans[x]=1;tot++;dfs(x-1);tot--;

	}

}

int main(){

	while(1){

		N=read();if(!N) break;

		REP(i,1,N) a[i].reset(),a[i][i]=a[i][N+1]=1;

		REP(i,1,N-1) {

			int u=read(),v=read();

			a[u][v]=a[v][u]=1;

		}

		res=inf;tot=0;

		Gauss(N,N+1);

		dfs(N);

		printf("%d\n",res);

	}

	return 0;

}

　　

2466: [中山市选2009]树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 735  Solved: 312
[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

 

[Submit][Status][Discuss]