比赛 |
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;
}