블 루 브리지 컵알고리즘 증가금속 채집 (트 리 동적 계획)

문 제 는 인류 가 화성 에서 새로운 금속 을 발견 했다 는 것 을 묘사 하고 있다!이 금속 들 은 이상 한 곳 에 분포 되 어 있 으 니 노드 라 고 불 러 도 무방 하 다.일부 노드 간 에 도로 가 연결 되 어 있 고 모든 노드 와 도로 가 나무 한 그루 를 형성 했다.모두 n 개의 노드 가 있 는데 이 노드 들 은 1 ~ n 으로 번 호 를 매 긴 다.인 류 는 이 금속 들 을 채집 하기 위해 k 개의 로봇 을 화성 으로 보 냈 다.이 로봇 들 은 모두 지 정 된 착지 점, S 번 노드 로 보 내 졌 다.모든 로봇 은 착륙 한 후에 반드시 도 로 를 따라 걸 어야 한다.로봇 이 한 노드 에 도 착 했 을 때, 그것 은 이 노드 에 매 장 된 모든 금속 광산 을 채집 할 것 이다.로봇 이 자신의 임 무 를 완성 한 후에 임의의 노드 에서 지구 로 돌아 갈 수 있다.물론 지구 로 돌아 온 로봇 은 더 이상 화성 에 갈 수 없다.우 리 는 이미 모든 도로 의 정 보 를 미리 측정 해 냈 는데, 그것 의 두 점 x 와 y, 그리고 이 도 로 를 통과 하 는 데 필요 한 에너지 w 를 포함한다.우 리 는 가능 한 한 적은 에 너 지 를 써 서 모든 노드 의 금속 을 채집 하고 싶다. 이 임 무 는 너 에 게 맡 길 것 이다.
입력 형식 첫 줄 은 세 개의 정수 n, S 와 k 를 포함 하고 각각 노드 의 개수, 착지 번호, 로봇 의 개 수 를 대표 합 니 다.다음은 모두 n - 1 줄 로 줄 마다 길 을 설명 합 니 다.한 줄 에는 세 개의 정수 x, y 와 w 가 포함 되 어 있 는데 이것 은 x 번 노드 와 y 번 노드 사이 에 길이 있 음 을 나타 내 고 w 개 단위 의 에 너 지 를 소비 해 야 한 다 는 것 을 의미한다.모든 도 로 는 양 방향 으로 통행 할 수 있다.출력 형식 은 모든 노드 의 금속 을 채취 하 는 데 필요 한 최소한 의 에 너 지 를 나타 내 는 정 수 를 출력 합 니 다.샘플 입력 613, 1, 2, 3, 2, 4, 1000, 25, 1000, 16, 1000 샘플 출력 3004 샘플 은 모든 로봇 이 1 번 노드 에 착륙 한 다 는 것 을 의미한다.첫 번 째 로봇 의 주 행 경 로 는 1 - > 6 이 고 6 번 노드 에서 지구 로 돌아 가 에 너 지 를 1000 으로 소모 한다.두 번 째 로봇 의 주 행 경 로 는 1 - > 2 - > 3 - > 2 - > 4 로 4 번 노드 에서 지구 로 돌아 가 에 너 지 를 1003 으로 소모 한다.첫 번 째 로봇 의 주 행 경 로 는 1 - > 2 - > 5 로 5 번 노드 에서 지구 로 돌아 가 에 너 지 를 1001 로 소모 한다.데이터 규모 와 약정 본 문 제 는 10 개의 테스트 포인트 가 있다.테스트 포인트 1 ~ 2, n < = 10, k < = 5.테스트 포인트 3, n < = 100000, k = 1.테스트 포인트 4, n < = 1000, k = 2.테스트 포인트 5 ~ 6, n < = 1000, k < = 10.테스트 포인트 7 ~ 10, n < = 100000, k < = 10.도로 의 에너지 w 는 모두 1000 을 초과 하지 않 는 정수 이다.
문제 풀이 방향: dp [root] [k]: 루트 를 뿌리 로 하 는 서브 트 리 에 k (소문 자 k) 로봇 의 비용 을 표시 합 니 다.반드시 주의해 야 할 것 은 하나하나 의 수 를 하나의 전체 로 간주 해 야 한 다 는 것 이다.좋 은 트 리 dp, 오래 이 해 했 습 니 다.
(1) 처음에 dfs 가 어느 노드 에 도 착 했 을 때 아들 노드 가 없 으 면 로봇 은 여기 서 멈 출 수 있 습 니 다. dp [root] [k] 는 0 입 니 다.
(2) 만약 에 아들 노드 가 발견 되면 이 아들 노드 에 remain (remain 의 수치 범 위 는 0, 1,..., k) 개 로봇 을 고려 합 니 다. / / 서브 트 리 슨 에 로봇 이 머 물 지 않 았 다 면 모두 되 돌아 가 는 것 을 의미 합 니 다. 적어도 한 개의 dp [root] [k] + = dp [next] [0] + cost * 2 를 되 돌려 줍 니 다.for (remain = 1; remain < = k; remain +) {/ / dfs 가 첫 아들 이 되 었 을 때 나머지 아들 을 잠시 발견 하지 못 했 기 때문에 루트 노드 에 남 은 로봇 은 dp [root] [k] = min (dp [root] [k], dp [root] [k - remain] + dp [next] [remain] + remain * cost) 을 소모 하지 않 습 니 다.}
(3) dfs 가 깊 어 지면 서 새로운 아들 을 발견 할 때마다 업 데 이 트 를 할 때 앞의 모든 아들 의 상 태 를 고려 하여 이전 해 야 한다.이것 은 점진 적 인 과정 이다.예 를 들 어 두 번 째 아들 때 k = 1, remain = 1 이면 dp [root] [k] = min (dp [root] [k], dp [root] [k - remain] + dp [next] [remain] + remain * cost);사용 하 는 dp [root] [k - remain] 은 더 이상 0 이 아 닙 니 다. 먼저 첫 번 째 아들 을 방문 하고 루트 노드 로 돌아 가 야 하기 때 문 입 니 다.모든 아들 dfs 가 지나 간 후에 얻 은 dp [root] [m] 는 더 이상 변 하지 않 습 니 다.
자바 코드:

import java.util.ArrayList;
import java.util.Scanner;

/** * @author   * */
public class Main {
    private static int n;//    
    private static int s;//     
    private static int K;//      
    private static Edge[] edge;//edge[i]:   i             
    private static boolean[] hasVisit;//           （             ）
    private static int[][] dp;//dp[p][k]:    p        k       。            

    /** * @param args */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        init();
        dfs(s);
        System.out.println(dp[s][K]);

    }

    private static void dfs(int root){
        hasVisit[root]=true;//            
        for(int i=0;i<edge[root].ends.size();i++){//i    root       i  
            int next=edge[root].ends.get(i);//next   root    i     
            int cost=edge[root].weights.get(i);
            if(hasVisit[next]){//        
                continue;
            }else{
                dfs(next);//     dp[next][0]、dp[next][1]、...、dp[next][K];
                for(int k=K;k>=0;k--){//         0   
                    dp[root][k]+=dp[next][0]+2*cost;//  son        ，       ，              
                    for(int remain=1;remain<=k;remain++){
                        int temp=dp[root][k-remain]+dp[next][remain]+remain*cost;//   son  remain       
                        if(temp<dp[root][k]){
                            dp[root][k]=temp;
                        }
                    }
                }
            }
        }   
    }


    //        （n、s、k、edge、dp、hasVisit）
    private static void init(){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        s=sc.nextInt();
        K=sc.nextInt();
        edge=new Edge[n+1];
        hasVisit=new boolean[n+1];
        dp=new int[n+1][K+1];
        for(int i=1;i<=n;i++){
            edge[i]=new Edge();
        }
        for(int i=1;i<=n-1;i++){
            int v1=sc.nextInt();
            int v2=sc.nextInt();
            int w=sc.nextInt();

            edge[v1].ends.add(v2);
            edge[v1].weights.add(w);

            edge[v2].ends.add(v1);
            edge[v2].weights.add(w);
        }
        sc.close();
    }
}

class Edge{
    ArrayList<Integer> ends=new ArrayList<Integer>();//              
    ArrayList<Integer> weights=new ArrayList<Integer>();//      
}