티스토리 뷰

카테고리 없음

Caves 풀이

알고리듬 2017. 11. 28. 16:42

문제 :  https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4153


노드의 개수가 N개인 가중치가 있는 rooted 트리가 주어집니다.

쿼리마다  root부터 시작해서 x 연료를 가지고 방문할 있는 노드의 최대개수를 출력해야 되는 문제입니다.


dp[i][j] = root i 서브트리에서, i 노드에서 출발해  j개의 노드를 방문하는데 드는 최소비용

bdp[i][j] = root i 서브트리에서, i 노드에서 출발해  j개의 노드를 방문하고 다시 i 돌아오는데 드는 최소비용


트리에서의 냅색처럼, dp 굴리면 됩니다.

현재 보고 있는 subtree root p,  현재 보고 있는 p 자식노드를 q , edge(p,q) =p,q사이의 거리라고 하면 아래와 같은 점화식을 만들 있습니다.

dp[p][i+j] = p 노드에서 (i+j)개의 노드를 방문하는데 드는 최소비용

bdp[p][i+j] = p 노드에서 (i+j)개의 노드를 방문하고 다시 p 돌아오는데 드는 최소비용

dp[p][i+j] = min(bdp[p][i] + dp[q][j] + edge(p,q) , dp[p][i] + bdp[q][j] + 2*edge(p,q)) 

bdp[p][i+j] = bdp[p][i] + bdp[q][j] + 2*edge(p,q) 





O( N^2 logN ) AC



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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;
const int MAXN = 502;
int dp[MAXN][MAXN],bdp[MAXN][MAXN];
int btdp[MAXN],tdp[MAXN]; //중복 계산을 피하기위한 가상의 dp공간
int N;
vector<pair<int,int> > tree[MAXN];
int ind[MAXN],root,sz[MAXN];
 
void dfs(int par){
    sz[par] = 1;
    dp[par][1= bdp[par][1= 0;
    for(int i=0;i<tree[par].size();i++){
        int son = tree[par][i].first;
        int w = tree[par][i].second;
        dfs(son);
        memset(tdp,0x3f3f3f3f,sizeof(tdp));
        memset(btdp,0x3f3f3f3f,sizeof(btdp));
        
        for(int i =1 ;i<=sz[par];i++){
            tdp[i] = min(tdp[i],dp[par][i]);
            btdp[i] = min(btdp[i],bdp[par][i]);
            forint j=0;j<=sz[son];j++){
                
                tdp[i+j] = min(tdp[i+j],bdp[par][i]+dp[son][j]+w);
                
                
                tdp[i+j] = min(tdp[i+j],dp[par][i]+bdp[son][j]+2*w);
                
                
                btdp[i+j] = min(btdp[i+j],bdp[par][i]+bdp[son][j]+2*w);
            }
        }
        
        sz[par]+=sz[son];
        for(int i=0;i<=sz[par];i++){
            dp[par][i] = tdp[i];
            bdp[par][i] = btdp[i];
        }
    }
}
int main(){
    int test = 0;
    while(scanf("%d",&N) == 1 && N){
        test++;
        printf("Case %d:\n",test);
        memset(ind,0,sizeof(ind));
        for(int i=1;i<=N-1;i++){
            int u,v,d; scanf("%d %d %d",&u,&v,&d);
            tree[v].push_back({u,d});
            ind[u]++;
        }
        for(int i=0;i<=N-1;i++){
            if(ind[i] == 0)root=i;
        }
        dfs(root);
        int Q; scanf("%d",&Q);
        for(int i=1;i<=Q;i++){
            int lim; scanf("%d",&lim);
            int ans = 1;
            for(int j=N;j>=1;j--){
                if(dp[root][j] <= lim){
                    ans = j; break;
                }
            }
            printf("%d\n",ans);
        }
        for(int i=0;i<MAXN;i++)tree[i].clear();
    }
    
    return 0;
}
cs


공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
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 30
31
글 보관함