AtCoder Beginner Contest 341-F
Problem
给你一个由 \(N\) 个顶点和 \(M\) 条边组成的简单无向图。每个顶点拥有权重\(W_i\),并且被放置了\(A_i\)个棋子。
只要图形上还有棋子,就重复下面的操作:
- 首先,从图形中选择一个(有棋子的)顶点\(x\)并移除一个棋子。
- 从\(x\)相邻点中选择出一些点组成集合\(S\)(可以不选),要保证这个集合内的所有点的权重之和小于顶点\(x\),即\(\sum_{y \in S} W_y \lt W_x\),并在\(S\)中的每个顶点上放置一个棋子。
请求出最多最多能进行多少次这样的操作。
可以证明,无论如何操作,在有限次迭代后,图形上将没有棋子。