记录编号	602680	评测结果	A
题目名称	2997.[POJ 1463]战略游戏	最终得分	100
用户昵称	Ruyi	是否通过	通过
代码语言	C++	运行时间	0.309 s
提交时间	2025-07-05 14:39:39	内存使用	3.88 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,num,fz1,fz2,f[1501],dp[1501][2],r;
char c;
vector<ll> t[1501];
void ff(int x){
    dp[x][0]=0;
    dp[x][1]=1;
    for(int i=0;i<t[x].size();i++){
        int s=t[x][i];
        ff(s);
        dp[x][0]+=dp[s][1];
        dp[x][1]+=min(dp[s][0],dp[s][1]);
    }
    return ;
}
int main(){
    freopen("strategic.in","r",stdin);
    freopen("strategic.out","w",stdout);
    while(cin>>n){
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=n;i++){
            cin>>num>>c>>c>>fz1>>c;
            for(int i=1;i<=fz1;i++){
                cin>>fz2;
                f[fz2]=num;
                t[num].push_back(fz2);
            }
        }
        while(f[r]!=r) r=f[r];
        ff(r);
        cout<<min(dp[r][0],dp[r][1])<<endl;
        memset(dp,0x3f,sizeof(dp));
        memset(f,0,sizeof(f));
        for(int i=0;i<n;i++) t[i].clear();
    }
}