Strategic game

题意：

给你一棵树，已知于某点放一个士兵，则与之相连的边就都能被“看守”，问使所有边都能有人看守至少要放置多少士兵。（本题为多组输入）

【与“没有上司的舞会”神似，经典树形dp】

思路：

树形dp为类似“树的后序遍历”的dfs, 由叶结点向根结点转移。

一条边要被看守，则其两端点至少要有一点有士兵。设 f[i] 为以 i 为根节点的子树所需最少士兵数，i 点有两种状态：放或不放。对于一条边，若 i 放置士兵，则该边所连的 i 的子结点可放可不放，取最小的一种；若 i 不放，则另一点必须放（否则这条边就无人看守了）。f[i][1]为放置，f[i][0]不放。则状态转移方程：

		f[i][1]=1+Σ(max(f[j][1],f[j][0]));
        f[i][0]=Σ(f[j][1]);

代码的实现上有两种写法：

一、单向边，求出根(root)再从root开始dfs

#include<algorithm>
#include<vector>
using namespace std;
const int M=1510;
int n,f[M][2];
vector<int> son[M];
void dfs(int i){
	f[i][1]=1;     //保证边界正确，就算为叶结点，后面的不执行，也正确。
	for(int x=0;x<son[i].size();x++){
		int j=son[i][x];
		dfs(j);
		f[i][1] += min(f[j][0],f[j][1]);
		f[i][0] += f[j][1];
	}
}
int main(){
	while(~scanf("%d",&n)){
		for(int i=0;i<n;i++){
			f[i][1]=f[i][0]=0;
			son[i].clear();
		}
		int root=n*(n-1)/2;  //先把所有点的和求出来
		for(int i=0,x,m;i<n;i++){
			scanf("%d:(%d)",&x,&m);
			for(int j=0,y;j<m;j++){
				scanf("%d",&y);//y是x的子节点
				root -= y;    //再依次减去子节点，最后剩下的就是根结点
				son[x].push_back(y);
			}
		}
		dfs(root);
		printf("%d\n",min(f[root][1],f[root][0]));
	}
	return 0;
}

二、存双向边，可以任意点为根结点开始搜索

#include<algorithm>
#include<vector>
using namespace std;
const int M=1510;
int n,f[M][2];
vector<int> son[M];
void dfs(int i,int fa){//定义一个fa（父亲）结点
	f[i][1]=1;
	for(int x=0;x<son[i].size();x++){
		int j=son[i][x];
		if(j==fa)continue;  //注意若与fa相等则不搜
		dfs(j,i);
		f[i][1] += min(f[j][0],f[j][1]);
		f[i][0] += f[j][1];
	}
}
int main(){
	while(~scanf("%d",&n)){//多组输入
		for(int i=0;i<n;i++){
			f[i][1]=f[i][0]=0;
			son[i].clear();  //清空
		}
		for(int i=0,x,m;i<n;i++){
			scanf("%d:(%d)",&x,&m);
			for(int j=0,y;j<m;j++){
				scanf("%d",&y);
				son[x].push_back(y);
				son[y].push_back(x);
			}
		}
		dfs(0,-1);    //这里以0为根结点搜
		printf("%d\n",min(f[0][1],f[0][0]));
	}
	return 0;
}