#Psmt12. 【例题2】新的开始

【例题2】新的开始

【例题2】新的开始

题目描述

发展采矿业当然首先得有矿井,小F花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井,但他似乎忘记考虑矿井的供电问题……

为了保证电力的供应,小F想到了两种办法:在这一口矿井上建立一个发电站,费用为v(发电站的输出功率可以供给任意多个矿井)。

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

小F希望你帮他想出一个保证所有矿井电力供应的最小花费。

输入格式

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

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

接下来为一个n*n的矩阵p,其中表示在第i口矿井和第j口矿井之间建立电网的费用(数据保证有pi,j=pj,i,且pi,ip_{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

提示

【样例解释】

小F可以选择在4号矿井建立发电站然后把所有矿井都与其建立电网,总花费是3+2+2+2=9。

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

对于100%的数据:1<=n<=300,0<=vi,pi,jv_i,p_{i,j}<=10^5。