AcWing 323. 战略游戏
原题链接
简单
作者:
最后五分钟
,
2023-08-05 04:21:34
,
所有人可见
,
阅读 57
#include<bits/stdc++.h>
using namespace std;
const int N=1510;
int e[N],ne[N],h[N],idx,f[N][2],st[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u)
{
f[u][1]=1;
f[u][0]=0;
for(int i=h[u]; ~i; i=ne[i])
{
int j=e[i];
dfs(j);
f[u][0]+=f[j][1];
f[u][1]+=min(f[j][0],f[j][1]);
}
}
int main()
{
int n;
while(cin>>n)
{
idx=0;
memset(st,0,sizeof st);
memset(h,-1,sizeof h);
int a,m;
while(n--)
{
scanf("%d:(%d)",&a,&m);
while(m--)
{
int b;
cin>>b;
add(a,b);
st[b]=1;
}
}
int fg=0,root;
while(st[fg]==1)fg++;
root=fg;
dfs(root);
cout<<min(f[root][1],f[root][0])<<endl;
}
return 0;
}