9999002 - 最优子图

本题为文件输入输出，输入文件名为 sub.in 。 第一行两个整数 , ，表示图中的节点个数，以及常数 。 接下来 行，每行 个整数 ，表示的意义如题所述。 其中 ，令有 表示此类边不存在。

对于 个节点的无向图，其中有 个节点为红色，另外 个节点为蓝色。 节点之间有以下连边关系，对于不同的 ： 相同颜色中的第 个节点与第 个节点之间的边权为 不同颜色中的第 个节点与第 个节点之间的边权为 其中 是一个给定的常数，且对于任意的 有 。 现在要在这些节点中，选出恰好 个节点，要求这些节点不完全同色。 找出一种选择方案，使得这 个节点之间边权的总和尽量大，输出这一最大值。

本题为文件输入输出，输出文件名为 sub.out 。 N ≤ K ≤ type = 9 ∼ 10 200 12 2 11 ∼ 12 3000 12 0 13 ∼ 14 3000 12 1 15 ∼ 20 3000 12 2 1 ≤ N ≤ 3000 1 ≤ K ≤ 12 type ∈ {0, 1, 2} 2N N N i, j i j wi,j i j K − wi,j K wi,j wi,j ≤ K ≤ 2 × wi,j N N N K K N N wi,j wi,j = wj,i wi,i = 0 输出一行，一个整数，表示子图边权和的最大值。