AcWing 323 . 战略游戏

题目传送门

这是基础课原题

#include 

using namespace std;

const int N = 1510;         //因为题目明确是有向图，无需M=N*2
int h[N], e[N], ne[N], idx; //邻接表
int f[N][2];
/**
 集合：    以结点i为 根节点 的子树，在 i 上放置哨兵(1) 和不放哨兵(0) 的方案
 状态表示： 方案中，放置的哨兵数量 最少
 状态计算：
 */
bool st[N];                 //用于判断是不是根节点

//邻接表模板
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

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];//节点u不放置哨兵，那么一定要从某一邻接节点放置哨兵
        f[u][1] += min(f[j][0], f[j][1]);//如果节点u放置了哨兵，那么邻接节点可以选择放置或者不放置
    }
}

int main() {
    //n组数据
    int n;
    //不断读入数据
    while (cin >> n) {
        //多组数据，清空邻接表
        memset(h, -1, sizeof h), idx = 0;
        //清空状态数组
        memset(st, 0, sizeof st);
        //n个节点
        for (int i = 1; i <= n; i++) {
            int x, m;
            scanf("%d:(%d)", &x, &m);//scanf可以按格式读入数据
            while (m--) {
                int y;
                cin >> y;
                //添加一条x->y的有向边
                //数据样例：1出发可以到达2,3;说明是有向图
                add(x, y);
                //标识y不是根
                st[y] = true;
            }
        }
        //有向图，需要找到出根
        int root = 0;
        while (st[root]) root++;

        //从根开始
        dfs(root);

        //输出 两个结果取个 min
        printf("%d\n", min(f[root][0], f[root][1]));
    }
    return 0;
}