题目链接：http://poj.org/problem?id=1463
题意：有N个点，每两个点至多只有一条边，如果在一个结点上放一个士兵，那他能看守与之相连的边，问最少放多少个兵，才能把所有的边能看守住。
分析：
1、dp[i][0]，表示在结点 i 没放置士兵的情况下，看住以结点 i 为根的子树的所有边所需的最少士兵；
2、dp[i][1]，表示在结点 i 放置士兵的情况下，看住以结点 i 为根的子树的所有边所需的最少士兵。
状态转移：
1、dp[i][0]=∑dp[j][1]，j 是 i 的儿子结点；（根结点不放士兵时，与其相连的边必须由儿子结点来看守，否则会出现两点没有士兵的情况）
2、dp[i][1]=dp[i][1]+∑ ( MIN ( dp[j][0] , dp[j][1] ) )，j 是 i 的儿子结点。 （根结点放士兵时，儿子结点可放可不放）
初始化： d[i][0]=0，d[i][1]=1，i是每一个节点
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 2010
#define clr(a) (memset(a,0,sizeof(a)))
using namespace std;
struct edge
{
int next,v;
edge(){}
edge(int v,int next):v(v),next(next){}
}e[N*];
int dp[N][],head[N],num[N],tot,n;
void addedge(int u,int v)
{
e[tot]=edge(v,head[u]);
head[u]=tot++;
}
void dfs(int u,int fa)
{
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
dp[u][]+=dp[v][];
dp[u][]+=min(dp[v][],dp[v][]);
}
}
int main()
{
int u,v,m;
while(scanf("%d",&n)>)
{
tot=;
memset(head,-,sizeof(head));
for(int i=;i<=n;i++)dp[i][]=,dp[i][]=;
for(int i=;i<n;i++)
{
scanf("%d:(%d)",&u,&m);
for(int j=;j<m;j++)
{
scanf("%d",&v);
addedge(u,v);
addedge(v,u);
}
}
dfs(,-);
printf("%d\n",min(dp[][],dp[][]));
}
}