【战略游戏】

题目

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1510, M = N;
int h[N], e[M], ne[M], idx;
int f[N][2];
int n;
bool st[N];
int root;
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u)
{
    f[u][1] = 1;
    for(int k = h[u]; ~k; k = ne[k])
    {
        int j = e[k];
        dfs(j);
        f[u][1] += min(f[j][0], f[j][1]);
        f[u][0] += f[j][1];
    }
}
int main()
{
    while(scanf("%d", &n) == 1)
    {
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        memset(f, 0, sizeof f);
        memset(e, 0, sizeof e);
        memset(ne, 0, sizeof ne);
        idx = 0;
        for(int i = 0; i < n; i++)
        {
            int a, cnt;
            scanf("%d:(%d)", &a, &cnt);
            for(int j = 0; j < cnt; j++)
            {
                int s;
                scanf("%d", &s);
                st[s] = true;
                add(a, s);
            }
        }
        for(int i = 0; i < n; i++)
        {
            if(!st[i]){
                root = i;
                break;
            }
        }
        dfs(root);
        printf("%d\n", min(f[root][0], f[root][1]));
    }

    return 0;
}

注意

每次要重置干净辅助空间