【BZOJ2466】[中山市选2009]树

Description

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

Input

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

Output

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

Sample Input

3
1 2
1 3
0

Sample Output

HINT

对于100%的数据，满足1 <= n <=100。

题解：明明O(n)就可以做的题看到网上那么多用高斯消元做的，还要枚举自由元，我就很不理解啊。

先设f[x][0/1]，g[x][0/1]这两个东西，它的意义是：f->摁x，g->不摁x，0->x不亮，1->x亮。所需要最少按多少次，然后就可以转移啦！从这几个角度入手列DP方程可能会快一些：

1.如果摁x，那么x的儿子都不亮；如果不摁x，那么x的儿子都要亮
2.如果x发亮，那么它和它的儿子中一定有奇数个点摁了；如果x不亮，那么它和它的儿子中一定有偶数个点摁了。

其实DP方程也不是那么繁琐~

注意：极大值不要开得太大！因为可能连续好多个状态都是不合法的，它们加起来就会爆~

#include <cstdio>#include <cstring>#include <iostream>using namespace std;int n,cnt;int to[210],next[210],head[110];int f[110][2],g[110][2];//f摁,g不摁,0不亮,1亮void dfs(int x,int fa){	int i,f0,f1,g0,g1;	g[x][1]=f[x][0]=n+1,f[x][1]=1,g[x][0]=0;	for(i=head[x];i!=-1;i=next[i])	{		if(to[i]==fa)	continue;		dfs(to[i],x);		f0=f[x][0],f1=f[x][1],g0=g[x][0],g1=g[x][1];		f[x][0]=min(f1+f[to[i]][0],f0+g[to[i]][0]);		f[x][1]=min(f0+f[to[i]][0],f1+g[to[i]][0]);		g[x][0]=min(g1+f[to[i]][1],g0+g[to[i]][1]);		g[x][1]=min(g0+f[to[i]][1],g1+g[to[i]][1]);	}}void add(int a,int b){	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}int main(){	while(1)	{		scanf("%d",&n),cnt=0;		if(!n)	return 0;		int i,a,b;		memset(head,-1,sizeof(head));		for(i=1;i<n;i++)	scanf("%d%d",&a,&b),add(a,b),add(b,a);		dfs(1,0);		printf("%d\n",min(f[1][1],g[1][1]));	}}

【BZOJ2466】[中山市选2009]树树形DP

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【BZOJ2466】[中山市选2009]树 树形DP