Problem1091--最小生成树21091: 最小生成树2
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 1 Solved: 1
[Status] [Submit] [Creator:]
Description
【题目描述】
大家还记得“西南旱灾”吗？我们有多少同胞没有水喝?“干净的水”对他们来说也是种奢望！当大家还在浪费水，洗澡还花上10几分钟，有没有觉得羞愧？西南地区的同胞生活在水深火热之中，yuyan的工程队特意赶到灾区挖井，以缓解旱情。
根据调查，工程队发现有N个地方缺水十分严重！工程队决定在这N个地方选择一些地方挖井，然后在某两个地方之间建立一条运输管道，通过管道把井水传输到其他地方，最后使这N个地方都有水供应！可是，因为地形的差异，每个地方挖水井所要付出的成本是不一定相同的！每两个地方之间建立管道所需要付出的成本也不一定相同。
现在，工程队估算出了每个地方挖井所需要的成本，每两个地方建立运输管道的成本。希望你能告诉他们：在哪些地方挖井，在哪些地方之间建立管道，才能使的总成本最小？同为炎黄子孙，为了广大的受苦同胞，作为中华儿女的你们，有责任去完成这个任务！
【输入格式】
一个整数N（1≤N≤300）表示N个地方严重缺水
以下N行，每行一个数，第I行的数为COSTi，表示在编号为i的地方挖水井所需的成本为COSTi
再接着N行，每行N个数，第I行第J个数X
表示在编号为I和编号J之间建造一条管道需要的成本是X
这个N*N的矩阵满足A[I,J]=A[J,I] A[I,I]=0
【输出格式】
一个整数，表示使得N个地方都有水的最小成本。
【样例输入】
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
【样例输出】
9
【数据约定】
对于20%的数据：N≤10
对于60%的数据：N≤100
对于100%的数据：N≤300, 所有成本≤100000
Hint：在编号为4的地方挖口井，成本为3
在1，2之间建一条管道，成本为2
在1，3之间建一条管道，成本为2
在1，4之间建一条管道，成本为2
至此，这4个地方都直接或间接有水供应，最小成本为3+2+2+2=9