問題概要
$n$ 頂点 $m $ 辺からなるグラフ $G = ( V, E )$ がある．ここで，$\forall u, ( u, u ) \not \in E$ かつ $( u, v ) \in E \Leftrightarrow ( v, u ) \in E$ である（i.e., $G$ は単純無向グラフである）．頂点 $u \in V$ には正整数 $W_u$ が紐付けられており，また，$A_u$ 個の駒が置かれている．
$G$ の頂点 $u \in V$ に対し，open neighbor $N( u )$ を
\begin{equation*}
N( u ) = \{ v \mid ( u, v ) \in E \}
\end{equation*}
で定義する*1．
駒が置かれている頂点が存在する限り，次の操作を繰り返す：
- $1$ つ以上の駒が置かれている頂点を選び，それを $x$ とする．
- $x$ から駒を $1$ つ取り除く．
- $N( x )$ の部分集合 $S \subseteq N( x )$ であって，$$\sum\limits_{ u \in S } W_u < W_x$$ なものを選ぶ．
- $S$ に含まれる頂点それぞれについて，新たな駒を $1$ つ置く．
最大で何回の操作を行えるか？ なお，無限回の操作を行うことはできない．
制約
- $2 \leq n \leq 5 \times 10^3$
- $1 \leq m \leq \min\left( \frac { n ( n - 1 ) } 2, 5 \times 10^3 \right)$
- $1 \leq W_u \leq 5 \times 10^3$
- $0 \leq A_u \leq 10^9$
解法
操作において $x$ や $S$ を毎回自由に選んでいると，あり得る操作手順の数が大きくなりすぎて扱えません．まずは何かよい性質が無いか探ってみます．
ある頂点に対して操作をして，その頂点から全ての駒が取り除かれた状況を考えてみます．このとき，この頂点に新たな駒が追加されることが無いことが保証されるならば，この頂点を操作対象にすることは二度とありません．そのような頂点が常にあるならば，頂点に順序を付けられます．$S$ に関する条件が $\sum\limits_{ u \in S } W_u < W_x$ と不等号で定義されていることから，$W_x = \max W$ な頂点 $x \in V$ に対して駒を追加できる頂点は存在しません．そのような $x$ から駒が無くなるまで連続して操作し，$V$ から $x$ を取り除くことを繰り返すことで，$x$ として選ぶ順序を固定できます．
次は $S$ の選び方について考えます．ある頂点における $S$ の選び方が複数あって，更にそれぞれによって新たに置かれる駒およびその子孫*2たちから稼ぎ出される操作回数の最大値が異なるという状況を考えます．このとき，稼ぎが少ない方の選び方をする代わりに稼ぎが多い方の選び方を採用することでよりよい解が得られることになるので，稼ぎが最大となる選び方のみを採用しなければならないことが分かります．
では，具体的な最適な $S$ の選び方はどのように決めればよいかというと，ある頂点 $u$ に由来する操作回数は $W_v < W_u$ なる頂点 $v$ たちにのみ依存するので，$W$ の値が小さい方から順に決めていくことができます．ある頂点に着目したときの $S$ の選び方の決め方は，ナップサック問題を解く超有名な DP とその復元になる*3ので，ここでは割愛します．
あとは，$W$ の値が大きい方から，駒が無くなるまで操作することを繰り返して……というか，着目している頂点にある駒全てにまとめて操作することを繰り返していけば，問題が解けます．
コード
constexpr auto INF = LIM< LL >::max() / 2; int main() { IN( int, N, M ); VVI G( N ); REP( M ) { IN( int, u, v ); --u, --v; G[u].PB( v ); G[v].PB( u ); } VI W( N ); VLL A( N ); cin >> W >> A; VI vertices( N ); iota( ALL( vertices ), 0 ); sort( ALL( vertices ), [&]( const int u, const int v ){ return W[u] < W[v]; } ); VLL rewards( N, 1 ); VVI add_to( N ); FOR( u, vertices ) { const int D = SZ( G[u] ); VVLL dp( D + 1, VLL( 5000, -INF ) ); // dp[ # of considerd vertices ][ sum of W ] := maximum rewards VVI prev( D + 1, VI( 5000, -1 ) ); dp[0][0] = 0; REP( i, D ) { REP( j, W[u] ) { if ( chmax( dp[ i + 1 ][j], dp[i][j] ) ) { prev[ i + 1 ][j] = j; } if ( j + W[ G[u][i] ] < W[u] && chmax( dp[ i + 1 ][j + W[ G[u][i] ] ], dp[i][j] + rewards[ G[u][i] ] ) ) { prev[ i + 1 ][ j + W[ G[u][i] ] ] = j; } } } int j = max_element( ALL( dp[D] ) ) - begin( dp[D] ); rewards[u] = 1 + dp[D][j]; for ( int i = D; 0 < i; --i ) { const int pj = prev[i][j]; if ( j != pj ) { add_to[u].PB( G[u][ i - 1 ] ); } j = pj; } } reverse( ALL( vertices ) ); LL res = 0; FOR( u, vertices ) { res += A[u]; FOR( v, add_to[u] ) { A[v] += A[u]; } } cout << res << endl; return 0; }
