HDU ACM 1054 Strategic Game 二分图最小顶点覆盖？树形DP「建议收藏」

#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;

#define N 1505
int dp[N][2];    //dp[i]表示以i为根节点时所须要的最小点数
int f[N];        //用来记录父节点
vector<int> son[N]; //记录儿子节点

int min(int x,int y)
{
	return x<y?x:y;}int dfs(int pos,int v){	int sum,i;	if(dp[pos][v]!=INT_MIN)		return dp[pos][v];	sum=v;	for(i=0;i<son[pos].size();i++)		if(v==1)                    //当前节点选			sum+=min(dfs(son[pos][i],0),dfs(son[pos][i],1));		else			sum+=dfs(son[pos][i],1);//当前节点不选，子节点必选	dp[pos][v]=sum;	return sum;}int main(){	int ans,n,i,x,m,j,t;	while(scanf("%d",&n)==1)	{		for(i=0;i<n;i++)		{			son[i].clear();			f[i]=i;			dp[i][0]=dp[i][1]=INT_MIN;		}		for(i=0;i<n;i++)		{			scanf("%d:(%d)",&x,&m);			for(j=0;j<m;j++)			{				scanf("%d",&t);				son[x].push_back(t);				f[t]=x;			}		}		for(i=0;i<n;i++)			if(f[i]==i)    //找到根节点			{				ans=min(dfs(i,0),dfs(i,1));				break;			}		printf("%d\n",ans);	}    return 0;}