http://acm.hdu.edu.cn/showproblem.php?pid=1054
树形DP 主要是把思路屡清楚
选个根结点进行向下搜 每个点都有两种可能 放士兵还是不放
防止重复搜索就可以
#include<iostream>
#include<string>
#include<string.h>
#include<queue>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
const int N=2000;
int yans[N];//此点放士兵 以此点为根结点的树的放士兵最小值
int nans[N];//此点不放士兵 以此点为根结点的树的放士兵最小值
bool had[N];//建的链表为双向 所以不能回搜 用作标记
struct node
{
struct tt *next;
}mem[N];
struct tt
{
struct tt *next;
int k;
};
inline void build(int i,int j)//建邻接表
{
struct tt *t=new tt;
t->k=j;
t->next=mem[i].next;
mem[i].next=t;
}
void freee(int n)//释放空间
{
struct tt *t;
for(int i=0;i<n;++i)
{
while(mem[i].next!=NULL)
{
t=mem[i].next;
mem[i].next=t->next;
delete(t);
}
}
}
int ydp(int x);
int ndp(int x)
{
if(nans[x]!=-1)//防止重复
return nans[x];
struct tt *t=mem[x].next;
nans[x]=0;//此点不放
while(t!=NULL)
{
if(!had[t->k])
{
had[t->k]=true;
nans[x]+=ydp(t->k);//此点不放 下边的点必须放
had[t->k]=false;
}
t=t->next;
}
return nans[x];
}
int ydp(int x)
{
if(yans[x]!=-1)
return yans[x];
struct tt *t=mem[x].next;
yans[x]=1;//此点放
while(t!=NULL)
{
if(!had[t->k])
{
had[t->k]=true;
yans[x]+=min(ydp(t->k),ndp(t->k));//此点放 下边的点可放 可不放 取最小
had[t->k]=false;
}
t=t->next;
}
return yans[x];
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i,j,m;
for(int l=0;l<n;++l)
{
scanf("%d",&i);
getchar();getchar();
scanf("%d",&m);
getchar();
while(m--)
{
scanf("%d",&j);
build(i,j);
build(j,i);
}
}
memset(yans,-1,sizeof(yans));
memset(nans,-1,sizeof(nans));
memset(had,false,sizeof(had));
had[0]=true;
printf("%d\n",min(ydp(0),ndp(0)));//以0为根结点 取最小
freee(n);
}
return 0;
}