题目链接：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*2]; int dp[N][2],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][0]+=dp[v][1];dp[u][1]+=min(dp[v][0],dp[v][1]);} } int main() {int u,v,m;while(scanf("%d",&n)>0){tot=0;memset(head,-1,sizeof(head));for(int i=0;i<=n;i++)dp[i][1]=1,dp[i][0]=0;for(int i=0;i<n;i++){scanf("%d:(%d)",&u,&m);for(int j=0;j<m;j++){scanf("%d",&v);addedge(u,v);addedge(v,u);}}dfs(1,-1);printf("%d\n",min(dp[1][0],dp[1][1]));} }