AcWing 323 . 戰略遊戲

題目傳送門

這是基礎課原題 AcWing 285. 沒有上司的舞會

#include <bits/stdc++.h>

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