题目链接：https://vjudge.net/problem/POJ-1463
简单题意：给定一棵树，士兵在一个结点可以看守相连的边，求最少数量的士兵，能看守所有的边。
这个和poj2342有点像。f[i][0/1]表示以i为根的子树边全部被看守，在i点不放/放士兵的最小值。则f[i][0]=Σf[j][1]，f[i][1]=Σmin(f[j][0],f[j][1])+1，和poj2342的方程也差不多。最后答案为min(f[root][0],f[root][1])。
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#define pb push_back
using namespace std;
const int maxn=2000+10;
vector<int> son[maxn];
int n,i,j,root,fa[maxn],f[maxn][2];
void dp(int u){
if (son[u].size()==0){
f[u][1]=1;f[u][0]=0; return;
}
for (int i=0;i<son[u].size();i++){
int k=son[u][i];
dp(k);
f[u][0]+=f[k][1];
f[u][1]+=min(f[k][0],f[k][1]);
}
f[u][1]+=1;
}
int main(){
std::ios::sync_with_stdio(false);
while (cin>>n){
char ch;
memset(fa,0,sizeof(fa));memset(f,0,sizeof(f));
for (i=0;i<maxn;i++) son[i].clear();
for (i=1;i<=n;i++){
int x,y,num;
cin>>x>>ch>>ch>>num>>ch;
for (j=1;j<=num;j++) {
cin>>y;
son[x].pb(y); fa[y]=1;
}
}
for (i=0;i<n;i++) if (fa[i]==0) root=i;
dp(root);
cout<<min(f[root][0],f[root][1])<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/edmunds/p/13497699.html