JOI春合宿 2009-day4 Distribution
問題文 : 冊子の配布
解法 :
得られるやる気を最大化したいので, 葉まで冊子を流し, その中の最大値を取っていけば良い.
つまり、葉までやる気を伝搬させれば良い.
この操作をM回繰り返す.
木の操作、最大値の取得をO(N)時間で行うことで, O(MN)時間でこの問題を解くことが出来る.
コード :
#include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> g[10000]; int mood[10000]; int tot[10000]; int par[10000]; int makeMax(int v, int s) { s += mood[v]; tot[v] = s; for (int i = 0; i < g[v].size(); i++){ makeMax(g[v][i], s); } } int main() { int n, m; int res; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++){ int a; scanf("%d %d", &a, &mood[i]); a--; if (~a) g[a].push_back(i); par[i] = a; } int ans = 0; for (int i = 0; i < m; i++){ makeMax(0, 0); int mP, mV; mP = mV = -1; for (int j = 0; j < n; j++){ if (tot[j] > mV){ mV = tot[j]; mP = j; } } ans += mV; for (; ~mP; mP = par[mP]){ mood[mP] = 0; } } printf("%d\n", ans); return (0); }