SRM622 Div1 Medium "Ethernet"
問題
TopCoder Statistics - Problem Statement
訳
あなたは0からN-1までの番号が付けられたN個のコンピュータを持っている。これらは1つのネットワークとして繋がっている。ネットワークの構造はツリー状になっている。あなたはその状態の説明としてint配列のparentとdistが与えられる。これらint配列は、ちょうどN-1個の要素を持つ。iを0からN-2としたとき、i+1番目のコンピュータはparent[i]番目のコンピュータとケーブルで繋がれており、その長さはdist[i]である。
あなたはまた次のような意味を持つint maxDistが与えられる。
同じネットワーク上にある、任意の2つのコンピュータの距離はmaxDistを超えてはならない。 (2つのコンピュータの距離はそれらを繋ぐケーブルの長さの合計とする)
もし、現在のネットワークが上記の性質を満たしていなければ、あなたはそれをより小さないくつかのネットワークに分割しなくてはならない。
形式的に言えば、あなたはまず小さなネットワークの数Kを決め、それからK個のネットワークの1つにそれぞれのコンピュータを配置する必要がある。それは下記のような性質を満たさなければならない。
- K個の新しいネットワークは元のツリーのサブツリーである。
- 新しいネットワークの直径は、大きくてもmaxDistでなければならない。
上記のような性質を満たすように、元のネットワークをK個の新しいネットワークに分割したときの、最小のKを返せ。
制約
1 <= コンピュータの数 <= 50
1 <= ケーブルの長さ <= 500
1 <= maxDist <= 500
解法
TopCoder SRM 622 Div1 Medium Ethernet - simezi_tanの日記
コチラを参考にしました。m(_ _)m
dfsで木DPする。
dp[v][d] = 頂点vを根とするサブツリーで、使える長さがdとしたときの、ケーブルを切る最小の数
サブツリーには使えるケーブルの長さに以下のような2つの制限がある。
①・・・頂点から末端までの長さ ②・・・サブツリー内の直径
①は簡単で、もしvの子供cのケーブルを切るのであれば、頂点cを根とするサブツリー上で使える長さはmaxDistまで回復するため、dfs(c, maxDist)としてやる。繋げたままとするのであれば、e(v, c)だけ使える長さが減るので、dfs(c, d - e(v, c))としてやればよい。
問題は②で、サブツリー上においても、直径はmaxDist以下としなくてはならない。サブツリー内の直径は、子供の末端までの距離上位2つの合計であるため、一番長い距離を使う子供と、その距離を決め打ちしてやる。そうすると他の子供の使える距離がでてくるので、①と②の小さいほうをdとしてdfsを呼べばよい。
ソースコード
int G[55][55]; int N, D; int dp[55][550]; class Ethernet { public: int connect(vector <int> parent, vector <int> dist, int maxDist) { N = parent.size(); D = maxDist; // グラフ作成 memset(G, -1, sizeof(G)); for (int i = 0; i < N; i++) { int v = i + 1; int u = parent[i]; int d = dist[i]; G[v][u] = G[u][v] = d; } // メモ初期化 memset(dp, -1, sizeof(dp)); return dfs(-1, 0, maxDist) + 1; } int dfs(int p, int v, int d) { int& res = dp[v][d]; if (res == -1) { res = 10000; // どの子を最長にしてやろうか?? for (int lc = 0; lc <= N; lc++) { if (G[v][lc] == -1 || lc == p) continue; //この子にどのくらいリソース分け与えてやろうか? for (int r = (D + 1) / 2; r <= D; r++) { int cand = 0; // 子で回す for (int c = 0; c <= N; c++) { if (G[v][c] == -1 || c == p) continue; // 切る int add = dfs(v, c, D) + 1; // 繋ぐ int rem = min(d, D - r); if (lc == c) rem = min(d, r); if (G[v][c] <= rem) add = min(add, dfs(v, c, rem - G[v][c])); cand += add; } res = min(res, cand); } } if (res == 10000) res = 0; } return res; } };