【战略游戏】
题目
代码
#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;
}注意
每次要重置干净辅助空间