Strategic game

题面描述

Bob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的路。注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被了望到。

例如，下面的树：

只需要放置1名士兵（在节点1处），就可观察到所有的边。

请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。

输入格式

输入文件中数据表示一棵树，描述如下：

第一行 N，表示树中结点的数目。

第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)，接下来k个数，分别是每条边的另一个结点标号r1，r2，…，rk。

对于一个n(0< n < =1500)个结点的树，结点标号在0到n-1之间，在输入文件中每条边只出现一次。

输出格式

输出文件仅包含一个数，为所求的最少的士兵数目。

样例

这个题就是一个选与不选的问题，因为如果这个点有士兵，他可以望到和这个点相邻的所有点，如果这个点选了，他的儿子就不选，如果儿子选了他就不选。dfs遍历到所有节点，然后回溯，如果儿子选了就找一个最小的，如果儿子没有选就加上。

代码

#include<bits/stdc++.h>
using namespace std;
const int oi=2000010;
int ver[oi],head[oi],edge[oi],f[oi],ne[oi],d1[oi],g[oi],s[oi],ans[oi],tot=0,sum=0,n,m;
void add(int x,int y)
{
	ver[++tot]=y;
	ne[tot]=head[x];
	head[x]=tot;
}
void dfs(int x,int y)
{
	g[x]=1;
	for(int i=head[x];i;i=ne[i])
	{
		if(ver[i]==y)
		continue;
		dfs(ver[i],x);
		f[x]+=g[ver[i]];
		g[x]+=min(f[ver[i]],g[ver[i]]);
	}
}
int main()
{
	freopen("strategi.in","r",stdin);
	freopen("strategi.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int p,l;
		cin>>l>>p;
		l++;
		for(int j=1;j<=p;j++)
		{
			int kl;
			cin>>kl;
			kl++;
			add(l,kl);
			add(kl,l);
		}
	}
	dfs(1,0);
	cout<<min(f[1],g[1]);
}