BZOJ-2466: [中山市选2009]树

[文章目录]

Description

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

话说高斯消元不是很懂啊。。。什么“搞死小圆一下+爆枚自由元”什么的,感觉我好菜啊。。
好像树形DP更优一些啊。。。设f[x][a][b]表示x按,不按,亮,不亮的方案数。推一推就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=200;//inf不能设太大,会加爆
int n;
int head[110],to[210],nxt[210],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
int f[110][2][2];
void dfs(int x,int pre)
{
    f[x][1][0]=f[x][0][1]=inf; f[x][0][0]=0; f[x][1][1]=1;
    int a,b,c,d,y;
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
    {
        y=to[i]; dfs(y,x);
        a=f[x][0][0],b=f[x][0][1],c=f[x][1][0],d=f[x][1][1];
        f[x][0][0]=min(b+f[y][1][1],a+f[y][0][1]);
        f[x][0][1]=min(a+f[y][1][1],b+f[y][0][1]);
        f[x][1][0]=min(d+f[y][1][0],c+f[y][0][0]);
        f[x][1][1]=min(c+f[y][1][0],d+f[y][0][0]);
    }
}
int main()
{
    while(1)
    {
        memset(head,0,sizeof head); cnt=0;
        scanf("%d",&n); int x,y;
        if(!n) return 0;
        for(int i=1;i!=n;++i)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        dfs(1,0);
        printf("%d\n",min(f[1][1][1],f[1][0][1]));
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注