NOIP2010提高组解题报告——Prison

【题目大意】

给定一个无向图。

我们用三个值来描述一条边:Edge.w(该边的权值),Edge.x,Edge.y(该边所相连的两个顶点)。

现需要把该图里的点分在两个集合A,B中。

令Weight_A=Max(Edge.w | Edge.x∈A,Edge.y∈A)

令Weight_B=Max(Edge.w | Edge.x∈B, Edge.y∈B)

则Answer=Max(Weight_A,Weight_B)

问Answer最小能是多少?

【算法分析】

本题有两种思路。

【算法一】

先二分答案,然后单独地判定可行性。

注意到二分答案Limit以后,使用所有Edge.w>Limit的边构成一个新图。然后这个可行性问题可以转化为:判定该新图是否一个二分图。

对于这个问题,我们可以通过对每个点黑白染色来判定。

染色过程如下:

使用广度优先搜索或者深度优先搜索遍历全图,对于一个连通分量,先对其中一个点染上白色。然后再将与它相邻的点都染成和该点相反的颜色。如此下去,不同连通分量分别处理,最后得到一个所有顶点都经过染色的图。然后检测是否存在一条边所连接的两个顶点颜色相同,若是,则不可行,否则可行。

【时间复杂度】O(V lg 10^9+E lg 10^9)

【空间复杂度】O(V+E)

【算法二】

注意到答案一定是某条边的权值,那么我们把边按权值从大到小排序,然后枚举答案,并考虑答案的改变,情况会发生什么变化。

答案每次减少一点,就会加入几条边,我们现在要在线判定新加边以后,该图是否还是二分图。那么我们用并查集维护每个连通分量,利用该点到并查集中根的距离判定染白色还是黑色。然后如果新加入一条边,连接同一连通块的两点并且他们到根的奇偶性相同,那么出现矛盾,不可行。否则,合并两个集合。

【时间复杂度】O(E lg E + V α(V))

【空间复杂度】O(V+E)

留下评论

您的电子邮箱地址不会被公开。