黑色騎士團的逆襲野望

https://tioj.ck.tp.edu.tw/problems/1394

Description

自從黑色騎士團上次的最終野望被白色騎士豬殺苦破滅之後，黑色騎士團銷聲滅跡了一陣子，不過他們仍繼續計畫著侵略神聖的大不列顛帝國。

終於他們發現了一個機會：原來大不列顛帝國的命脈就是對外輸出的藥品"REBRAIN"，只要能控制住它所有的運輸與加工途徑，那大不列顛帝國就完了！

與之前一樣，他們只要佔領一個據點就可以控制與他相鄰的運輸途徑了！

“REBRAIN"的運輸過程十分有趣，他有一個總工廠來製造"REBRAIN"的一些半成品，再依序經過幾個有向道路到下個加工地點進行加工，就這樣一直到完成成品，並且為了不讓產品流程出問題，他們的運輸路徑不會出現環狀或逆向的情況。

不過黑色騎士團的人手有限，所以他們希望佔據最少的據點就可以完全控制整個運輸與加工途徑。

註: 雖然是有向邊，不過相鄰的關係依然是互相的；另外雖然沒有講的很清楚，題目是有保證0號節點可以走到所有其他節點

Solution

題目所求是最小點覆蓋，也就是在給定圖上要選幾個點才能保證所有邊都有一個端點被選到
因為這題給的是DAG，所以我們可以考慮用DP的方式做

狀態$dp[i][s]$代表$i$往子孫走的邊都已經保證有端點被選到的答案，若$s=1$代表有選$i$這個點，反之沒有
可以知道如果沒有選$i$這個點，那他的子節點都一定要選，所以
$$dp[i][0] = \sum\limits _ {j\in son(i)} dp[j][1]$$
如果選了$i$這個點，那他的子節點可選可不選，我們就取比較小的那個，有
$$dp[i][1] = 1 + \sum\limits _ {j\in son(i)} \min(dp[j][0],dp[j][1])$$

最後取的答案是0號節點選或不選取$\min$

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <bits/stdc++.h>
using namespace std;
const int N = 33001;

int dp[N][2], vis[N];
vector<int> g[N];
void dfs(int i) {
    if(vis[i]) return;
    vis[i] = true;
    dp[i][0] = 0;
    dp[i][1] = 1;
    for(int j:g[i]) {
        dfs(j);
        dp[i][0] += dp[j][1];
        dp[i][1] += min(dp[j][0],dp[j][1]);
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n,k;
    cin >> n;
    for(int i = 0,k; i < n; i++) {
        cin >> k;
        g[i].resize(k);
        for(int &j:g[i]) cin >> j;
    }
    dfs(0);
    cout << min(dp[0][0], dp[0][1]) << '\n';
}