我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:爱彩网 > 二分图 >

求 关押罪犯 标程

归档日期:07-01       文本归类:二分图      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件。

  每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。

  在详细考察了N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使Z 市长看到的那个冲突事件的影响力最小?这个最小值是多少?

  输出共1 行,为Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件,请输出0。

  由于市长只会去看列表中的由大至小第一个事件的影响力,那么,我们所要求的就是这样的一个最大值。现在,题目要求这样的一个最大值要尽可能的“小”。什么意思?其实就是说,我们通过一定的分配罪犯监狱的方法分配完罪犯之后,那么对于分进两个不同的监狱中的罪犯将不存在怨气值,因而,不同的分法可能存在着不同的最大值。因而,现在我们要做的就是,找出这样的分配方法,使得其中最大的怨气值是所有可行分配方法中最小的一个值。

  首先,我们会发现题目中有一个重要的大前提:就是S城只有两座监狱!这样的一句话,可以很明显的让我们看出本题所具有的二分图的性质,因为通过可行分配方法分配过后,所有的罪犯将会被分进两个不同的监狱,抽象起来就是二分图的模型。那么,本题是否用到了二分图的算法呢?答案是没有,因为我们真正需要的仅仅是对于二分图是否成立的一个定性的判断。

  到以上,我们就有了一个粗略的想法:就是通过枚举的思想,枚举最大的边,将比它大的边删去,那么,对于剩下的图来说,如果我们能够将之划分成二分图,则当前所枚举的最大边就将是一个可行的解。并且,我们可以想到的一个判断二分图的可行方法就是宽度搜索:将图中的一个没选过的点标上1,与之相连的点标上2,然后再依次标上1,2......,当然,如果其中出现了矛盾,则说明这个图不可二分。

  至此,我们得到了一个可行的算法:枚举最大的边,宽搜判断二分图。 时间的复杂度约为O(M*N)。朴素的30分。

  进一步思考,发现在枚举最大边时,我们可以想到的一个很好的优化,那就是:二分枚举!因为,我们可以通过排序,使得边由小到大递增,那么边的顺序就具有了单调性,因而,我们可以采用二分的思想来枚举。效率就会立马提升一个档次。

  完善后:时间复杂度约为O(N*logM)。从理论上将已经可以通过全部的点了。

  然而细细的想后,会发现在我们判断二分图的时候,每次都是在一个新的图上判断二分图能否成立,因而,判断一遍二分图约是O(N)级别的效率,这样可以看出,效率被花在的二分图的判断上。那么,我们是否可以改善一下判断的方法呢?

  再次回顾一下题目中的大前提,我们发现:罪犯被分在了两个监狱,也即是分成了两类!同类在一个监狱!我们可以将每一类之抽象成一个集合。

  那么在动态维护每一类的对象,以及便于查找确定每个对象所在类别的数据结构是什么呢?很明显:并查集!

  想到并查集之后,问题就简化了许多。现在我们可以采取的解决办法就是:将所有的边排序,然后由大到小将每条边一次删去,对于每一条删去的边来说,边上所连接的两个点需要被分在两个不同的集合之中(即将这两个罪犯分在不同的监狱)。当我们在删去边的时候,发现该边上所连接的两个点已经在同一类集合之中了,那么此时,这条边就是不可被删去的。也就是最终的解。时间复杂度约为O(5*M)(该常数是并查集的效率)

  对于并查集,我们可以采用的办法由两种:一种是同类合并。另一种是关系合并。

  对于当前这条待删去的边来说,我们需要判断边上所连接的两个点是否曾经有过关系,如果不曾有过关系,则说明这两个点可以成为敌对的关系;反之,需要我们判断当前这两点的关系是否敌对,如果不敌对则说明当前这条边是不可删去的,否则是可以删去的。

  路径压缩的时候,我们需要修改点的父亲,以及点与父亲的关系。合并的时候,我们也需要建立一个点与其父亲的关系。(在个人标程中有详细的说明。)

  if s[a[i]]=s[b[i]] then {当二者之前发生过关系,并且现在的关系和之前的关系相矛盾,则说明当前的为输出解}

  writeln(0);{删去所有的边后仍然符合条件,则说明此时应当输出0}

本文链接:http://pikeducation.com/erfentu/459.html