• [A] Kill All

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • 恶魔神官为了杀死年幼的勇者,他便想发动一场恐慌。

    恶魔神官命令一个恶魔变成人类混在了 n-2 个平民中,这样恶魔与平民的总数就是 n-1 了,加上勇者就是 n 个人了,这 n 个人会开始一场疯狂的运动,运动的方式就是杀人。一个人可以杀多个人,一个人也可以被多个人追杀。当一个人存在被别人追杀的情况,他就会想要去杀掉他想要杀的那个人或那几个人。当某个人不被追杀时,他便不会再去杀别人。不存在两个人互杀的情况,即当a想杀b,那么b不可能想杀a。而且每个人之间会存在这样一个关系,当一个人杀死另一个人时,会产生一个损失值。

    现在告诉你这 n 个人的追杀与被追杀的关系以及之间的损失值,而且这些关系中,恶魔会一直追杀他想要追杀的人,因为他的目的就是想杀死勇者;但另一些人(善良的平民)是无奈才去追杀别人,只要这些人(善良的平民)的追杀者消失,他们也会停止追杀别人。

    现在你是女神,你发现了这个秘密,你想让其中的几个人被他的追杀者杀死以确保平息暴乱,即使是勇者死掉也没关系。但是你是善良的,希望这个损失值的和值最小。请问,你该怎么办才能使这个损失值的和值最小?这 n 个人的编号是 1 到 n ,恶魔的编号是1,勇者的编号是 n ,勇者不但有被杀的能力,还有杀人的能力= =。勇者被追杀,为了保命去消灭魔王,他也只能反抗了。
  • 输入
  • 第一行输入两个正整数 n (4 <= n <= 100)和 m (n - 1 <= n <= n * (n - 1) / 2),m 代表这次动乱中有 m 条关系。接下来有 m 行,每行代表一个关系,每个关系存在三个数 x, y 和 v,表示 x 会追杀 y,当 x 杀掉 y,那么会产生的损失值是 v (0 < c < 100)。
    输入保证不会存在两个人互杀的情况。
  • 输出
  • 输出最小损失值。
  • 样例输入
  • 4 3
    1 3 1
    2 3 1
    3 4 1
    
  • 样例输出
  • 1
    
  • 提示
  • 来源
  • Hungar
  • 操作

显示春菜