Vijos 1021 Victoria的舞会1 解题报告

这题实际上就是要求一个图中的最大点集，要求点集中的每个点的度不小于k。不过据说数据太弱，只需要将初始度小于k的点剔除即可，不需要对删边进行处理。

还是简单说一下我的做法吧，先将初始度小于k的点剔除，并且将与其连接的点的度减1，在此过程中如果有某个点的度被剪到小于k则加入队列并标记已经处理过。然后对队列中的点做同样处理，一直到没有点可以加入队列，扫一次所有点的度，统计不小于k的点的个数输出即可。由于每个点最多入队一次，所以时间复杂度是O(n^2)。

R1191343 Accepted 100 From IwfWcf－ P1021 FPC Vivid Puppy 2009-3-28 21:37:25