AcWing 1077. 황궁 간수 (나무형 DP) 문제 풀이

제목 전송 문
제목 설명
태평 왕세자 사건 이후 육 소 봉 은 황제 가 특별히 초빙 한 어전 품 시위 가 되 었 다.
황궁 은 오문 을 기점 으로 후궁 빈궁 들 의 침실 까지 나무 모양 으로 어떤 궁전 들 은 서로 볼 수 있다.
대내 보위 가 삼엄 하고 세 걸음 한 걸음, 다섯 걸음 한 걸음 보초 가 있 으 며 모든 궁전 은 전 천후 에 지 키 는 사람 이 있어 야 하 며 서로 다른 궁전 에서 지 키 는 데 필요 한 비용 이 다르다.
그러나 육 소 봉 은 경비 가 부족 해서 어떻게 든 궁전 마다 시 위 를 지 킬 수 없 었 다.
육 소 봉 이 시 위 를 배치 하 는 것 을 도와 모든 궁전 을 지 키 는 전제 에서 비용 이 가장 적 게 든다.
입력 형식
입력 중 데이터 설명 트 리 는 다음 과 같 습 니 다.
첫 번 째 줄 n 은 나무의 결점 수 를 나타 낸다.
두 번 째 줄 에서 n + 1 줄 까지 모든 궁전 의 노드 정 보 를 묘사 합 니 다. 그 다음 에 이 궁전 의 노드 레이 블 i, 이 궁전 에 시위 에 필요 한 경비 kk, 이 노드 의 자 결 점 수 m, 그 다음 m 개 수 는 각각 이 노드 의 mm 키 노드 의 레이 블 r1, r2, rm 입 니 다.
n 개의 노드 트 리 에 대해 노드 레이 블 은 1 에서 n 사이 이 고 레이 블 은 중복 되 지 않 습 니 다.
출력 형식
하나의 정 수 를 출력 하여 가장 적은 경 비 를 표시 하 다.
데이터 범위
1≤n≤1500
입력 예시:
6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0
출력 예시:
25
샘플 설명:
2, 3, 4 결점 에 호 위 를 배치 하면 궁전 전 체 를 관찰 할 수 있 으 며 필요 한 경비 가 16 + 5 + 4 = 25 로 가장 적다.
문제 풀이:
트 리 DP:
f [N] [3] 은 3 가지 상 태 를 나타 낸다. 0 은 아버지 노드 가 수 비 를 놓 았 다 는 뜻 이 고 1 은 아들 노드 가 수 비 를 놓 았 다 는 뜻 이 며 2 는 자신 이 수 비 를 놓 았 다 는 뜻 이다.
f [u] [0] + = min (f [j] [i], f [j] [2]) 부모 노드 가 수 비 를 놓 으 면 바이트 점 을 놓 을 수 있 고 놓 지 않 을 수 있 습 니 다. 우 리 는 최소 값 을 가 집 니 다.
f [u] [2] + = min (f [j] [0], min (f [j] [1], f [j] [2]) 자신 이 수 비 를 놓 았 습 니 다. 하위 노드 는 놓 아 도 되 고 놓 지 않 아 도 되 며 3 가지 상태의 최소 치 를 제거 합 니 다.
사고 서브 노드 가 수 비 를 놓 은 상황:
어느 하위 노드 가 수 비 를 놓 았 는 지, 즉 f [j] [2] 를 열거 합 니 다. 다른 하위 노드 는 놓 을 수 있 고 놓 지 않 을 수 있 습 니 다. 먼저 sum 으로 하위 노드 값 의 총 계 를 구 할 수 있 습 니 다. 즉, f [u] [0] 입 니 다.
f [u] [0] - min (f [j] [1], - f [j] [2]) 은 j 라 는 하위 노드 의 다른 하위 노드 의 총 계 를 제거 하 는 것 을 나타 낸다.
출시: f [u] [1] = min (f [u] [1], f [j] [2] + f [u] [0] - min (f [j] [1], f [j] [2]);

#include
#include
using namespace std;
const int N = 1510;
int h[N], e[N], w[N], ne[N], idx;
int f[N][3];  //3    0          ,1          ,2         
int n, m, a, b, c;
int vis[N];
void add(int a, int b)
{
     
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
     
    f[u][2] = w[u];
    int sum = 0; //        f[j][1], f[j][2]     
    for(int i = h[u]; i != -1; i = ne[i]){
     
        int j = e[i];
        dfs(j);
        f[u][0] += min(f[j][1], f[j][2]);
        f[u][2] += min(f[j][0], min(f[j][1], f[j][2]));
    }
    f[u][1] = 1e9;
    for(int i = h[u]; i != -1; i = ne[i]){
     
        int j = e[i];
        //      j     
        //f[u][0] - min(f[j][1], - f[j][2])     j             ;
        f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2])); 
    }
}
int main()
{
     
    cin >> n;
    memset(h, -1, sizeof h);
    memset(vis, false, sizeof vis);
    for(int i = 1; i <= n; i++){
     
        cin >> a >> c >> m;
        w[a] = c;
        while(m--){
     
            cin >> b;
            add(a, b);
            vis[b] = true;
        }
    }
    int root = 1;
    while(vis[root])root++;  //     
    dfs(root);
    cout << min(f[root][1], f[root][2]) << endl;
    return 0;
}