Tag Archives: 1000pt

一切1000pt都是纸老虎之SRM435

前言:

这里的1000pt是指Topcoder的算法类比赛中难度最大占分最高的那一道题,SRM是Single Round Match的缩写,是TC里最常见的一类算法比赛。1000pt的难度如果从ACM比赛的角度来看应算作中等偏难,但由于SRM的比赛时间紧迫(75分钟3道题)再加上不是实时返回结果,想做对的难度还是不小的(至少对我来说是这样)。之前的SRM比赛里我只注重成绩,往往来不及在比赛中做1000pt的题,结束以后也往往就不管不顾了,现在我深刻认识到自己的错误,于是打算对比较经典的1000pt难题进行一系列的分析。为了保证时效性,我尽量在每场比赛结束后官方的题解发布前写出题解,敬请关注,嘿嘿。

正文:

今天要说的是SRM 435的1000pt题目(原题见这里),题目大意是,某公司计划重组管理结构,使所有人员形成一个“森林”状结构,即若干树的集合,每个人只属于一棵树,也就是每个人至多有一个上司,要求树的个数尽可能少。这个公司在之前曾有过一些暂时管理关系,比如A曾经暂时管理过B,B可能也暂时管理过A。如果A暂时管理过B,那么A就认为他比B优秀,而且这种优越感是可传递的,即如果A管理过B,B管理过C,则A也认为他比C优秀。如果A认为自己B优秀,B也认为自己比A优秀,就说两个人有“互斥优越感”。现在要求重组后得到的森林状结构满足:

1. 任何人的下属应该是他曾经管理过的人。

2. 不应有任何人认为他比自己的直接上司优秀。

3. 有“互斥优越感”的人不应当有同一个上司。

分析:

首先,如果A曾经管理B,我们就连有向边(A,B),那么“互斥优越感”这个东西很容易让人想到强连通分量(SCC),一个SCC内部的所有人都是互斥的。我们首先考虑没有SCC的情况,这时候图是一个有向无环图(DAG),类比DAG上的最小路径覆盖问题,这题我们求的是“最小树覆盖”。如果仍套用拆点的思路,即:把每个点x拆成左右两个点x和x’,原来的边(x,y)变成新边(x,y’)得到二分图。我们会发现唯一的不同之处是,允许左边的点匹配多个右边的点,而这个只需把匹配扩展到最大流问题即可求解。

当然,无SCC的情况是trivial的,实际上我们无需求助于流直接数一下入度为0的点就可以了。但加上SCC以后问题就变得略有复杂。由条件(2),可知同一SCC内的点不可能互为上司下属关系,即若原图中有边(x,y)且x,y属于同一SCC,我们直接把这边忽略,不把它加到流网络里;由条件(3),可知同一SCC内的点不能有同一上司,即在新二分图里同一SCC的多个点不能“匹配”到左侧的同一个点上,这一限制条件不能用简单的二分图表示,我们可以再新加一列结点(三分图?),每个结点表示一个SCC,让原来二分图的边通过这个中转点卡一下,再分发出去,这样就可以表示出条件(3)的限制。具体建图过程如下:

1. 若x管理y,则连边(x,y),得到一个有向图G。对此图求强连通分量。

2. 构建网络G2:

2a. 把G中每个点x拆为两个点x和x’,再把G的每个强连通分量当作一个点,同时新加源S和汇T

2b. 对于G中的边(x,y),若x,y不属于同一SCC,则在G2中加边(x, scc[y]) (如果此边不存在的话),容量为1,再加边(scc[y], y’),容量为1。这里scc[y]表示y所属的scc。

2c. 从S到每个左侧点x加边,容量为INF

2d. 从每个右侧点x’到T加边,容量为1

3. 求G2的最大流F,则n-F即为所求