#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 15100
#define M 151000
using namespace std;
int n,son[M],next[M],fa[N],in[N],dp[M][4],root;
void add(int u,int v)
{
	next[v]=son[u]; son[u]=v; fa[v]=u;
}
void read()
{
	memset(son,-1,sizeof son);
	memset(next,-1,sizeof next);
	memset(in,0,sizeof in);
	int a,b,c;
	for(int i=1;i<=n;i++)
	{
		scanf("%d:(%d)",&a,&b);
		for(int j=1;j<=b;j++)
		{
			scanf("%d",&c);
			add(a+1,c+1);
			in[c+1]++;
		}
	}
}
void getroot()
{
	for(int i=1;i<=n;i++)
	   if(in[i]==0) {root=i;break;}
}
int search(int x,int pd)//覆盖边！！ 
{
    if(dp[x][pd]<=9999999) return dp[x][pd];
    if(pd==0)//x父节点没有人看 
    {
        if(next[x]==-1&&son[x]==-1) return dp[x][pd]=1;
        else if(next[x]==-1&&son[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],1+search(son[x],1));
        } 
        else if(son[x]==-1&&next[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],search(next[x],0)+1);
        } 
        else 
        { 
            dp[x][pd]=min(dp[x][pd],1+search(son[x],1)+search(next[x],0));
        } 
        return dp[x][pd]; 
    } 
    else//x的父亲结点有人看 
    {
        if(next[x]==-1&&son[x]==-1) return dp[x][pd]=0;
        else if(next[x]==-1&&son[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],1+search(son[x],1));
            dp[x][pd]=min(dp[x][pd],search(son[x],0));
        } 
        else if(son[x]==-1&&next[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],search(next[x],1));
        } 
        else 
        { 
            dp[x][pd]=min(dp[x][pd],search(son[x],0)+search(next[x],1));
            dp[x][pd]=min(dp[x][pd],search(son[x],1)+1+search(next[x],1));
        }
        return dp[x][pd]; 
    } 
    
    /*覆盖点版！！ 
    if(dp[x][pd]<=9999999) return dp[x][pd]; 
	if(pd==0)//父节点已经覆盖 
	{
        if(next[x]==-1&&son[x]==-1) return dp[x][pd]=0; 
        else if(next[x]==-1&&son[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],search(son[x],2));
		    dp[x][pd]=min(dp[x][pd],search(son[x],0)+1);
        } 
        else if(son[x]==-1&&next[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],search(next[x],0));
        } 
        else
        { 
            dp[x][pd]=min(dp[x][pd],search(son[x],2)+search(next[x],0));
    		dp[x][pd]=min(dp[x][pd],search(son[x],0)+1+search(next[x],0));
    	} 
		return dp[x][pd];
	}
	else if(pd==2)//本节点和其子节点之一必须要放置一个 
	{
        if(next[x]==-1&&son[x]==-1) return dp[x][pd]=1; 
        else if(next[x]==-1&&son[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],search(son[x],0)+1);
            dp[x][pd]=min(dp[x][pd],search(son[x],1));
        } 
        else if(son[x]==-1&&next[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],search(next[x],2)+1);
        } 
        else
        {
            dp[x][pd]=min(dp[x][pd],search(son[x],0)+1+search(next[x],0));
            dp[x][pd]=min(dp[x][pd],search(son[x],1)+search(next[x],0));
        } 
        return dp[x][pd];
    }
    else//本节点(或兄弟节点)必须放置 (其父节点必由父节点的子节点覆盖) 
    {
        if(son[x]==-1&&next[x]==-1) return dp[x][pd]=1;
        else if(son[x]==-1&&next[x]!=-1)
        {
            dp[x][pd]=min(dp[x][pd],search(next[x],2)+1);
        }
        else if(son[x]!=-1&&next[x]==-1)
        {
            dp[x][pd]=min(dp[x][pd],search(son[x],0)+1);
        } 
        else
        { 
            dp[x][pd]=min(dp[x][pd],search(son[x],0)+1+search(next[x],2));
            dp[x][pd]=min(dp[x][pd],search(son[x],1)+search(next[x],1));
             
        } 
        return dp[x][pd];
    }*/ 
}
void go()
{
	memset(dp,0x7f,sizeof dp);
	dp[root][0]=search(root,0);
	printf("%d\n",dp[root][0]);
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		read();
		getroot();
		go();
	}
	system("pause"); 
	return 0;
}

• Re:原来是覆盖边，我写了个覆盖点的。。。 (12) lagoon0o0 2012-07-15 20:56:48
• 一语惊醒梦中人。。orz~ (0) ULTMaster 2015-07-21 13:59:49