比赛 |
2025暑期集训第4场 |
评测结果 |
A |
题目名称 |
战略游戏 |
最终得分 |
100 |
用户昵称 |
KKZH |
运行时间 |
0.109 s |
代码语言 |
C++ |
内存使用 |
4.14 MiB |
提交时间 |
2025-07-05 10:54:16 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
long long n,m;
long long f[1510],dp[1510][2],z[1510],l[1510];
vector <long long> e[1510];
void dfs(long long u){
dp[u][0]=0;
dp[u][1]=1;
for(long long i=0;i<e[u].size();i++) {
long long v=e[u][i];
dfs(v);
dp[u][0]+=dp[v][1];
dp[u][1]+=min(dp[v][0],dp[v][1]);
}
}
int main(){
freopen("strategic.in","r",stdin);
freopen("strategic.out","w",stdout);
// std::ios::sync_with_stdio(false);
while(cin>>n){
memset(f,0,sizeof(f));
memset(dp,1,sizeof(dp));
memset(z,1,sizeof(z));
memset(l,0,sizeof(l));
for(long long i=0;i<n;i++) e[i].clear();
long long y,deep=0,x=0,r=0;
long long a;
for(long long i=0;i<n;i++){
scanf("%lld:(%lld)",&a,&m);
for(long long j=0;j<m;j++){
scanf("%lld",&y);
l[y]=1;
e[a].push_back(y);
f[y]=i;
}
}
long long rt;
for(long long i=0;i<n;i++)
if(l[i]==0) {
rt=i;
continue;
}
dfs(rt);
printf("%lld\n",min(dp[rt][0],dp[rt][1]));
}
return 0;
}