OI题库

【题目描述】

发展采矿业当然首先得有矿井，  小  FF  花了上次探险获得的千分之一的财富请人在岛

上挖了 n 口矿井，  但他似乎忘记考虑的矿井供电问题……

为了保证电力的供应，  小 FF 想到了两种办法：

1、  在这一口矿井上建立一个发电站，  费用为  v（发电站的输出功率可以供给任

意多个矿井）。

2、  将这口矿井与另外的已经有电力供应的矿井之间建立电网，  费用为 p。

小 FF 希望身为”NewBe_One"  计划首席工程师的你帮他想出一个保证所有矿井电力供

应的最小花费。

【输入格式】

第一行一个整数 n，  表示矿井总数。

第 2～n+1 行，每行一个整数，  第 i 个数 v[i]表示在第 i 口矿井上建立发电站的费用。

接下来为一个 n*n 的矩阵 P，  其中 p[ i , j ]表示在第 i 口矿井和第 j 口矿井之间建立

电网的费用（数据保证有 p[ i, j ] = p[ j, i ],  且  p[ i, i ]=0）。

【输出格式】

仅一个整数，  表示让所有矿井获得充足电能的最小花费。

【输入样例】

4

5

4

4

3

0 2 2 2

2 0 3 3

2 3 0 4

2 3 4 0

【输出样例】

9

输出样例说明：

小 FF 可以选择在4号矿井建立发电站然后把所有矿井都与其建立电网，总花费是

3+2+2+2 = 9。

【数据范围】

对于30%的数据：      1<=n<=50;

对于100%的数据：    1<=n<=300;      0<=v[i], p[i,j] <=10^5.