#背包

AtCoder Beginner Contest 341-F

F - Breakdown Problem给你一个由 个顶点和 条边组成的简单无向图。每个顶点拥有权重 ，并且被放置了 个棋子。 只要图形上还有棋子，就重复下面的操作： 首先，从图形中选择一个（有棋子的）顶点 并移除一个棋子。 从 相邻点中选择出一些点组成集合 （可以不选），要保证这个集合内的所有点的权重之和小于顶点 ，即 ，并在 中的每个顶点上放置一个棋子。 请求出最多最多能进行多少次这样的操作。 可以证明，无论如何操作，在有限次迭代后，图形上将没有棋子。