题目描述

又到了一年一度的明明生日了，明明想要买 B 样东西，巧的是，这 B 样东西价格都是 A 元。 但是，商店老板说最近有促销活动，也就是： 如果你买了第 I 样东西，再买第 J 样，那么就可以只花 K(I,J)元，更巧的是，K(I,J)竟然等于 K(J,I)。 现在明明想知道，他最少要花多少钱。 【输入格式] 第一行两个整数，A,B。 接下来 B 行，每行 B 个数，第 I 行第 J 个为 K(I,J)。我们保证 K(I,J)=K(J,I) 并且 K(I,I)=0。 特别的，如果 K(I,J)=0，那么表示这两样东西之间不会导致优惠。注意 K(I,J)可能大于 A。

输入格式

无

输出格式

一个整数，为最小要花的钱数。

样例

输入样例 1

1 1
0

输出样例 1

1

提示

数据规模：1≤B≤500,0≤A,K(I,J) ≤1000。

思路：用Kruskal建立最小生成树（MST）。 1.将每件物品视作一个节点，物品之间的优惠或费用为边的权值。 2.设置一个序号为零的节点（精髓所在） ， 此点直接连接的节点即为通过花费 a 元直接购买的物品。 3.每一样物品都可通过直接花费a元来购买，所以从节点零向每一个节点连接一条权值为a的边。 4.优惠购买 = 边权 K(I,J). 5.正常建边，正常Kruskal 。求连接所有节点的最小代价。