티스토리 뷰
문제 : 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]); for( int 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 |