seuOJ101 - 数学建模

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：秋季, 校赛, 2018

题目描述

cqh 喜欢的妹子最近迷上了数学建模，所以他也只好爱屋及乌，妹子最近被一道题目难住了：

国家决定准备通过在建立核电站和架设特高压输电线来解决供电问题。

在第 $i$ 号地区中建设核电站需要花费 $W_i$元；而架设连接 $i$ 号地区与 $j$ 号地区的一条特高压输电线需要花费 $P_{ij}$元。

对于每一个地区，该地区必须建有核电站或者与任意数量的建有核电站的地区通过由一条或多条特高压输电线组成的路径连接，它才能通上电。

请求出国家给所有地区供电所需要的最小花费。

根据套路，cqh 决定请你帮忙完成这个题目。

输入格式

本题包含多组测试数据，输入的第一行表示测试数据组数 $T(1\leq T\leq 10)$。

对于每组测试数据：第 $1$ 行为一个整数 $n(1\leq n\leq 300)$；第 $2$ 到 $n+1$ 行每行一个整数，其中第 $i+1$ 行的整数表示 $W_i(1\leq W_i\leq 10^5)$；第 $n+2$ 到 $2n+1$ 行每行 $n$ 个整数，其中第 $i+n+1$ 行的第 $j$ 个整数表示 $P_{ij}(1\leq P_{ij}\leq 10^5,\ P_{ji}=P_{ij})$ 。

输出格式

对于每组测试数据，输出一行，为一个整数，表示所需要的最小花费。

样例

样例输入

1
4
5
4
4
3
0 2 2 2 
2 0 3 3
2 3 0 4
2 3 4 0

样例输出

9

样例解释

国家应该在第 $4$ 号地区建设核电站，然后将各地与 $1$ 号地区相连($3+2+2+2=9$)。