P1550 [USACO08OCT] Watering Hole G
题目描述
Farmer John 的农场缺水了。
他决定将水引入到他的 $n$ 个农场。他准备通过挖若干井,并在各块田中修筑水道来连通各块田地以供水。在第 $i$ 号田中挖一口井需要花费 $W_i$ 元。连接 $i$ 号田与 $j$ 号田需要 $P_{i,j}$($P_{j,i}=P_{i,j}$)元。
请求出 FJ 需要为使所有农场都与有水的农场相连或拥有水井所需要的最少钱数。
输入格式
无
输出格式
无
说明/提示
对于 $100\%$ 的数据,$1 \leq n \leq 300$,$1 \leq W_i \leq 10^5$,$0 \leq P_{i,j} \leq 10^5$。