比赛 2025暑期集训第4场 评测结果 W
题目名称 战略游戏 最终得分 0
用户昵称 rb_tree 运行时间 0.070 s
代码语言 C++ 内存使用 3.89 MiB
提交时间 2025-07-05 09:56:36
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
void write(int x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar((x%10)^48);
}
const int N=1500,M=3005;
int n,dp[N][3];
int h[N],nxt[M],to[M],_cnt;
void add_edge(int a,int b)
{
    to[++_cnt]=b;
    nxt[_cnt]=h[a];
    h[a]=_cnt;
}
void init()
{
    memset(dp,0x3f,sizeof(dp));
    memset(h,0,sizeof(h));
    memset(nxt,0,sizeof(nxt));
    memset(to,0,sizeof(to));
    _cnt=0;
}
void dfs(int x,int f)
{
    dp[x][0]=1;
    dp[x][2]=0;
    for(int i=h[x];i;i=nxt[i])
    {
        int v=to[i];
        if(v==f) continue;
        dfs(v,x);
        dp[x][0]+=min(dp[v][0],dp[v][2]);
        dp[x][2]+=dp[v][1];
    }
    for(int i=h[x];i;i=nxt[i])
    {
        int v=to[i];
        if(v==f) continue;
        dp[x][1]=min(dp[x][1],dp[x][2]-dp[v][1]+dp[v][0]);
    }
}
signed main()
{
    freopen("strategic.in","r",stdin);
    freopen("strategic.out","w",stdout);
    int n;
    while(scanf("%d",&n)==1)
    {
        init();
        for(int i=1;i<=n;i++)
        {
            int u=read(),m=read();
            for(int j=1;j<=m;j++)
            {
                int v=read();
                add_edge(u,v);
                add_edge(v,u);
            }
        }
        dfs(0,0);
        write(min(dp[0][0],dp[0][1]));
        putchar('\n');
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}