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

ZJU/ZOJ 1935 XYZZY 解题报告

题目大意是从点1出发，初始有100分，达到每个房间会减少或增加一定分数，问能否以正分到达点n（中间过程也必须是正分）。每个房间可经过多次。

先判断n到1的联通性，如果无法联通自然直接判不可到达。然后在与n联通的房间中从1开始找最长路，但由于一个房间可以经过多次，所以可能存在正权圈，而如果存在正权圈则到达n时必定可保证为正分。故可用Bellman-Ford或SPFA来找正权圈，如果存在正权圈（Bellman-Ford更新了n次仍无法结束、SPFA单个点入队次数大于等于n）或在更新过程中n的最长距离大于0则可判定可达，否则判定不可达。

3009544 2008-07-27 22:21:28 Accepted 1935 FPC 00:00.01 428K IwfWcf

ZJU/ZOJ 1119 SPF 解题报告

题目大意是求给出的图中的割顶以及其所分割的子网数。

求割顶的方法非常简单，以对每个点的连接点作DFS一直到覆盖其所有连接点为止，达到覆盖所有连接点时所作的DFS次数就是子网数。注意本题数据中给出的图是一个非常稀疏的图，所以可以用邻接表优化空间储存效率。

3008859 2008-07-27 15:21:01 Accepted 1119 FPC 00:00.00 424K IwfWcf