Skip to content

1194: 灌水

题目

题目描述

Farmer John 的农场缺水了。

他决定将水引入到他的 $n$ 个牧场。他准备通过挖若干井,并在各块田中修筑水道来连通各块田地以供水。在第 $i$ 号田中挖一口井需要花费 $W_i$ 元。连接 $i$ 号田与 $j$ 号田需要 $P_{i,j}$元。

请求出 FJ 需要为使所有农场都与有水的农场相连或拥有水井所需要的最少钱数。

输入格式

第一行为一个整数 $n$。

接下来 $n$ 每行一个整数 $W_i$。

接下来 $n$ 行,每行 $n$ 个整数,第 $i$ 行的第 $j$ 个数表示连接 $i$ 号田和 $j$ 号田需要的费用 $P_{i,j}$。

输出格式

输出一行一个整数,表示所需要的最少钱数。

样例输入

4

5

4

4

3

0 2 2 2

2 0 3 3

2 3 0 4

2 3 4 0

样例输出

9

数据范围

对于 $100\%$的数据,$1 \leq n \leq 300,1 \leq W_i \leq 10^5,1 \leq P_{i,j} \leq 10^5,$ 且 $P_{j,i}=P_{i,j},P_{i,i}=0$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!