Strategic game树形DP解法(Poj1463,Uva1292)

已经写过本题用二分图的做法，见这儿。

本题的图是一棵树，求最小点覆盖也可以用树形DP的做法。

定义状态f[0/1][u]表示以u为根的子树，u选取/不选最少需要选取多少点来覆盖。

显然 f[0][u] = Sigma{f[1][v]},f[1][u] = Sigma{min(f[0][v],f[1][v])}+1 ( < u,v > 属于G且v!=u.father)

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN=2000+5;

int hd[MAXN],outd[MAXN];

int n,cnt;

struct Edge

{

	int t,n;

}e[MAXN<<1];

int f[2][MAXN];

inline void build(int f,int t)

{

	e[++cnt]=(Edge){t,hd[f]};

	hd[f]=cnt;

	++outd[f];

}

void dfs(int u,int fa)

{

	for(int i=hd[u];i;i=e[i].n)

	{

		int v=e[i].t;

		if(v==fa)

			continue;

		dfs(v,u);

		f[0][u]+=f[1][v];

		f[1][u]+=min(f[1][v],f[0][v]);

	}

	++f[1][u];

}

int main()

{

	while(~scanf("%d",&n))

	{

		cnt=0;

		memset(hd,0,sizeof hd);

		memset(e,0,sizeof e);

		memset(f,0,sizeof f);

		memset(outd,0,sizeof outd);

		int to,from,m;

		for(int i=0;i<n;++i)

		{

			scanf("%d:(%d)",&from,&m);

			for(int i=1;i<=m;++i)

				scanf("%d",&to),build(from,to),build(to,from);

		}

		dfs(0,0);

		printf("%d\n",min(f[0][0],f[1][0]));

	}

	return 0;

}