恶魔神官为了杀死年幼的勇者,他便想发动一场恐慌。
恶魔神官命令一个恶魔变成人类混在了 n-2 个平民中,这样恶魔与平民的总数就是 n-1 了,加上勇者就是 n 个人了,这 n 个人会开始一场疯狂的运动,运动的方式就是杀人。一个人可以杀多个人,一个人也可以被多个人追杀。当一个人存在被别人追杀的情况,他就会想要去杀掉他想要杀的那个人或那几个人。当某个人不被追杀时,他便不会再去杀别人。不存在两个人互杀的情况,即当a想杀b,那么b不可能想杀a。而且每个人之间会存在这样一个关系,当一个人杀死另一个人时,会产生一个损失值。
现在告诉你这 n 个人的追杀与被追杀的关系以及之间的损失值,而且这些关系中,恶魔会一直追杀他想要追杀的人,因为他的目的就是想杀死勇者;但另一些人(善良的平民)是无奈才去追杀别人,只要这些人(善良的平民)的追杀者消失,他们也会停止追杀别人。
现在你是女神,你发现了这个秘密,你想让其中的几个人被他的追杀者杀死以确保平息暴乱,即使是勇者死掉也没关系。但是你是善良的,希望这个损失值的和值最小。请问,你该怎么办才能使这个损失值的和值最小?这 n 个人的编号是 1 到 n ,恶魔的编号是1,勇者的编号是 n ,勇者不但有被杀的能力,还有杀人的能力= =。勇者被追杀,为了保命去消灭魔王,他也只能反抗了。