2015/2/4

leaf posted @ 2015年2月04日 21:45 in 未分类 , 460 阅读

今天被一道裸的最小割虐出翔了。。

 为了增加军队的战斗力,D国建立了两所重要的军事院校 A和 B, 每年为军
队培养人才。这两所军校所培养的学生最终都分配到两个重要的军事科研院X和
Y中。 
已知今年A和B分别毕业nA和nB个毕业生, A校的毕业生从1到nA编号,
B 校的毕业生从 nA + 1 到 nA + nB编号。他们每个人都对两个科研院有自己的评
分,编号为 i 的毕业生对 X 和 Y 的评分分别为 ui和 vi。评分是一个整数,可能
一个毕业生不喜欢某一个科研院,因此他的评分可能是负数。 
在工作的时候,如果同一个学校的毕业生在同一个研究院工作,他们会很默
契的配合,如果两个毕业生 a和b来自不同的院校,他们需要花费 Cab的磨合成
本。 
栋栋今年负责两校毕业生的分配,他想知道,他怎么分配毕业生,能使得最
终所有毕业生对自己分配到的院校的评分和, 再减去在一起工作的不同院校的磨
合成本最高。
我死活想不出。。囧
我只会减去不在同一个集合的。。。在相同集合不会。。没思考出来。。
 
后来经诸位orz讲解,原来这是两个不同种类之间在同一个集合。。将一种的S,T交换一下即可,这样相同集合就变成不同集合,可以最小割解决。。
 
orz吴大神,随机乱搞70。。这个得学学,不会要乱搞。。。

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter