7981번: 장비를 정지합니다

https://www.acmicpc.net/problem/7981

$O(n+\sum r)$

DFS를 활용한 DP로 쉽게 해결할 수 있다.
dp[i]를 i번 장비를 정지시키기 위해 필요한 최소 전력이라고 정의하자.
i번 장비에 약한 충격을 가했을 때 다시켜지는 장비 리스트를 aj라 하면
dp[i]=min(u[i]+sum(dp[aj]),z[i]) 이다.
이렇게 풀다보면 dp[aj]를 구해놓지 않은 경우가 있을 수도 있다.
이런 경우에는 사이클 상의 장비 중 적어도 하나는 강한 충격이 가해질 것이므로 i번 장비에 강한 충격을 가해도 상관없다.
(아래 소스에서는 dp[aj]=z[aj]라고 가정했다.)
사이클 상의 모든 장비가 약한 충격이 가해졌다면 dp값이 무한정 증가하는 모순이 생기기 때문이다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 2e5;
int u[MXN + 1], z[MXN + 1], n, ck[MXN + 1];
vector<int> adj[MXN + 1];
int f(int h) {
    if (!ck[h]) {
        ck[h] = 1;
        long long s = u[h];
        for (auto it : adj[h]) s += f(it);
        if (z[h] > s) z[h] = s;
    }
    return z[h];
}
int main() {
    scanf("%d", &n);
    for (int i = 1, r; i <= n; i++) {
        scanf("%d%d%d", u + i, z + i, &r);
        for (int j = 0, x; j < r; j++) {
            scanf("%d", &x);
            adj[i].push_back(x);
        }
    }
    printf("%d", f(1));
    return 0;
}