比赛 20101101 评测结果 AAAAAAAAAA
题目名称 树的最大匹配 最终得分 100
用户昵称 kaaala 运行时间 0.004 s
代码语言 C++ 内存使用 3.18 MiB
提交时间 2012-11-05 09:28:59
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

using namespace std;

struct edge
{
	int t;
	edge *next;
	edge(int _t,edge *_next):t(_t),next(_next){}
}*Map[1001];

int N;
long long f[1001][2],g[1001][2];
bool flag[1001];

inline void addedge(int s,int t)
{
	Map[s]=new edge(t,Map[s]);
}

void dp(int u)
{
	g[u][1]=1;
	for(edge *p=Map[u];p;p=p->next)
	{
		dp(p->t);
		int t=p->t;
		f[u][1]+=f[t][0];
		g[u][1]*=g[t][0];
	}
	long long k=0;
	f[u][0]=f[u][1];
	for(edge *p=Map[u];p;p=p->next)
	{
		int t=p->t;
		if(f[t][1]+1>f[t][0])
		{
			f[u][0]=f[u][1]+1;
			g[u][0]+=g[u][1]/g[t][0]*g[t][1];
		}
		if(f[u][0]==f[u][1]&&f[t][1]+1==f[t][0])
			k+=g[u][1]/g[t][0]*g[t][1];
	}
	if(f[u][0]==f[u][1])
		g[u][0]=g[u][1]+k;
}

int main()
{
	freopen("treeb.in","r",stdin);
	freopen("treeb.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		int a,b,c;
		scanf("%d%d",&a,&c);
		for(int j=1;j<=c;j++)
		{
			scanf("%d",&b);
			addedge(a,b);
			flag[b]=true;
		}
	}
	for(int i=1;i<=N;i++)
		if(!flag[i])
		{
			dp(i);
			N=i;
			break;
		}
	printf("%lld\n%lld",f[N][0],g[N][0]);
	return 0;
}