【算法设计与分析】（8）游戏问题（树形DP）

问题描述

小李很喜欢玩计算机游戏，特别是战略游戏，但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题：他必须在一个中世纪的城堡里设防，城堡里的道路形成一棵无向树（连通图）。要在结点上安排最少的士兵使得他们可以看到所有边。你能帮助他吗？

你的任务是给出士兵的最少数目。

输入格式

输入包含多组数据。每组数据表示一棵树，在每组数据中：

第一行是结点的数目。

接下来的几行，每行按如下格式描述一个结点：

结点标识符 : ( 道路的数目 ) 结点标识符1 结点标识符2 ...... 结点标识符

或者

结点标识符 : (0)

对于 n (0<n<=1500) 个结点，结点标识符是一个从 0 到 n - 1 的整数。每条边在测试用例中只出现一次。

输出格式

对于每组数据，各给出一个整数表示士兵的最少数目.

例如：

输入： （注意：由于显示问题，测试时请去掉"0: (1)”中冒号和左括号之间的空格。）

4

0: (1) 1

1: (2) 2 3

2: (0)

3: (0)

5

3: (3) 1 4 2

1: (1) 0

2: (0)

0: (0)

4: (0)

输出：

1

2

这道题是树形DP，但有个简单算法，优先删除所有孤立的点和度为1的点，然后在度为1点的父节点放置士兵，循环直到所有点都被删除

#include<stdio.h>
#include<string.h> 
 int n=0,i=0,j=0,k=0,dp[3000][3000],a[3000],a1=0,a2=0,a3=0,count=0;
 
 int main()
 {
  while (scanf("%d",&n)!=EOF)
  {
   count=0;
   memset(a,0,sizeof(a));
   memset(dp,0,sizeof(dp));
   
   for (i=0;i<n;i++)
   {
   	scanf("%d:(%d)",&a1,&a2);
   	a[a1]=a[a1]+a2;
   	for (j=0;j<a2;j++)
   	{
   	 scanf("%d",&a3);
	 dp[a1][a3]=1;
	 dp[a3][a1]=1;
	 a[a3]++;	
	}
   }
   
   int num=n;
   while (num>0)
   {
   	
   	for (i=0;i<n;i++)
   	if (a[i]==1&&a[i]==0)//度为1的点和孤立的点删除
   	{
   	 num--;
	 a[i]=0;
	 break;
	} 
	
	 for(j=0;j<n;j++)
	 if (dp[i][j]==1)
	 {
	  dp[i][j]=0;
	  dp[j][i]=0;
	  num--;
	  count++; //度为1的点的父亲结点放置士兵
	  a[j]=0;
	  for (k=0;k<n;k++)
	  if (dp[j][k]==1) //删除该点及叶子结点
	  {
	   	if (a[k]==1)
	   	{
	   	 num--;
		 a[k]=0;
		 dp[j][k]=0;
		 dp[k][j]=0;	
		}
		else 
		{
		 a[k]--;
		 dp[j][k]=0;
		 dp[k][j]=0;	
		}
	  }	
	 }	
	
   }
   printf("%d
",count);
  }
  return 0;
 }