【战略游戏】

题目

代码

#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;
}

注意

每次要重置干净辅助空间