AcWing 1077. 황궁 간수 (상세 설명)

제목 설명
        태평 왕세자 사건 이후 육 소 봉 은 황제 가 특별히 초빙 한 어전 품 시위 가 되 었 다.황궁 의 각 궁전 의 분 포 는 한 그루 의 나무 모양 으로 궁전 은 나무 속 의 결점 으로 볼 수 있 고 두 궁전 사이 에 도로 가 직접 연결 되 어 있 으 면 이 도 로 는 나무 중의 한 변 으로 볼 수 있다.한 궁전 에서 지 키 는 수 비 는 본 궁전 의 상황 을 관찰 할 수 있 을 뿐만 아니 라 이 궁전 과 도로 가 직접 연 결 된 다른 궁전 의 상황 도 관찰 할 수 있 는 것 으로 알려 졌 다.대내 보위 가 삼엄 하고 세 걸음 한 걸음, 다섯 걸음 한 걸음 보초 가 있 으 며 모든 궁전 은 전 천후 에 지 키 는 사람 이 있어 야 하 며 서로 다른 궁전 에서 지 키 는 데 필요 한 비용 이 다르다.그러나 육 소 봉 은 경비 가 부족 해서 어떻게 든 궁전 마다 시 위 를 지 킬 수 없 었 다.육 소 봉 이 시 위 를 배치 하 는 것 을 도와 모든 궁전 을 지 키 는 전제 에서 비용 이 가장 적 게 든다.
입력 형식
입력 중 데이터 설명 트 리 는 다음 과 같 습 니 다.
첫 줄 n, 나무의 결점 수 를 나타 낸다.
두 번 째 줄 에서 두 번 째 줄 까지 n+1 줄 마다 각 궁전 의 노드 정 보 를 묘사 하고 그 다음은 이 궁전 의 노드 레이 블 이다. i, 이 궁전 에 시위 배치 에 필요 한 경비 k, 결산 해 야 할 자 결산 포인트 다음 m 개수 m 키 점 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 [i] [3] 를 만 듭 니 다.

f [i] [0] 은 i 번 째 노드 가 부모 노드 에 설 치 된 수위 가 간호 하 는 최소 대가

를 나타 낸다.

f [i] [1] 는 i 번 째 노드 가 하위 노드 에 설 치 된 수위 간호 하의 최소 대가

를 나타 낸다.

f [i] [2] 는 i 번 째 노드 가 이 노드 에 설 치 된 수위 가 간호 하 는 최소 대가

라 고 밝 혔 다.
그러면 이전 관 계 를 쓸 수 있 습 니 다.

f[i][0] += min(f[j][1], f[j][2]);

f[i][1] = min(f[i][1], sum - min(f[j][1], f[j][2]) + f[j][2]);

f[i][2] += min(min(f[j][0], f[j][1]), f[j][2]);

그 중에서 j 는 i 의 서브 노드 이 고 sum 은 모든 서브 노드 j 의 min (f [j] [1], f [j] [2] 의 합 이 며 1 과 3 의 의미 가 뚜렷 하 다.
이로써 알고리즘 의 사고방식 이 뚜렷 해 졌 다. 다음은 일반적인 구 해 과정 으로 코드 를 쓴다.       
코드

#include 
#include 
#include 
#include 
using namespace std;


const int N = 1510;

int n;
int h[N], e[N], ne[N], idx,w[N];
int f[N][3];
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][2] = w[u];

    int sum = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += min(f[j][1], f[j][2]);
        f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
        sum += min(f[j][1], f[j][2]);
    }

    f[u][1] = 1e9;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        f[u][1] = min(f[u][1], sum - min(f[j][1], f[j][2]) + f[j][2]);
    }
}


int main()
{
    cin >> n;

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int id, cost, cnt;
        cin >> id >> cost >> cnt;
        w[id] = cost;
        while (cnt -- )
        {
            int ver;
            cin >> ver;
            add(id, ver);
            st[ver] = true;
        }
    }

    int root = 1;
    while (st[root]) root ++ ;

    dfs(root);

    cout << min(f[root][1], f[root][2]) << endl;

    return 0;
}