← 返回题目列表

AtCoder · icpc2013summer_day2_f

F. 社交怪物

中文机器翻译题面 查看原题

一个神秘生物和人类互相帮助生活的世界。 在这个世界上,有很多锦标赛,你捕获的怪物会相互竞争。 许多男孩和女孩的目标是成为世界上最好的教练。

在锦标赛中,你用捕获的怪物创建一个队伍,并且队伍之间互相战斗。 怪物对之间是有兼容性的,有兼容性很差的情况,也有兼容性一般的情况。 如果兼容性很差,你就不能让这对怪物在同一队伍中。 如果兼容性正常的话 兼容性由数值友情度表示。 在战斗中,全队的友好度总和是胜利的关键。

现在N来自怪物K我想创建一个由怪物组成的队伍。 M怪物对 兼容性已知为(a_i,   b_i)和整数 它由 c_i 表示。 当 c_i = 0 时,a_i 与怪物 b_i 怪物的兼容性非常差。 c_i  ≠  0 时,a_i 与怪物 b_i 与怪物的兼容性正常,友好度为 c_i 。 给定 除M对外,兼容性正常,且所有友好度均为0。

让我们考虑一下如何选择一个使友谊级别总和最大化的政党。

入力形式

输入按以下格式给出

N M K
a_1 b_1 c_1
...
a_M b_M c_M

出力形式

K如果无法创建一支由一只怪物组成的队伍,请在一行上打印“Impossible”。
当可以组队时,输出友好度总和的最大值。

制約

  • 1 ≤ K ≤ N ≤ 2000
  • 0 ≤ M ≤ N
  • 1   ≤   a_i   ≠   b_i   ≤ N
  • |c_i|   ≤ 10000
  • 每个怪物都是 它在 a_1, a_2, …, a_M, b_1, b_2, …, b_M 中最多出现两次。
  • i   ≠   j   ⇒   \{a_i, b_i\}   ≠   \{a_j,   b_j\}

入出力例

入力例 1

6 5 4
2 1 1
2 5 2
5 1 1
4 3 2
3 6 -1

出力例 1

4

入力例 2

3 1 3
1 2 -10

出力例 2

-10

入力例 3

6 3 5
1 2 0
2 3 10
3 4 0

出力例 3

Impossible