代码解释

#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N=1510;
int n;
int h[N],e[N],ne[N],idx;
int f[N][2];
bool st[N];

void add(int a,int b)  //建立边
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

//状态表示为：以u为根节点的子树，1代表选这个点的方案，0代表不选这个点的方案
//类似于上司的舞会
void dfs(int u)
{
    f[u][0]=0,f[u][1]=1;//不选   选
    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()
{
        cin>>n;
        memset(h,-1,sizeof h);//初始化表头
        idx=0;
        memset(st,0,sizeof st);//初始化数组

        for(int i=0;i<n;i++)
        {
            int id,cnt;
            scanf("%d:(%d)",&id,&cnt);
            while(cnt--)
            {
                int ver;
                cin>>ver;
                add(id,ver);  //在id这个城市和另外的cnt的城市之间建图
                st[ver]=true;//标记孩子节点
            }
        }
        int root=0;
        while(st[root])   root++;   //寻找根节点
        dfs(root);

        printf("%d\n",min(f[root][0],f[root][1]));  //最少的士兵数

    return 0;
}