道路规划

题目描述

有 N 个村庄，编号从 1 到 N，请你建立一些道路，使得任意两个村庄可以相连。我们说两个村 A 和 B 是相连的，当且仅当有一条公路在 A 与 B 之间，或存在一个村庄 C，有一条的道路连接着 A 和 C 之间，一条连接着 B 和 C。

我们知道，已经有一些道路在一些村庄之间，你的工作是再建一些道路，使得所有的村庄连接并且所有的道路建造总和最低。

输入格式

第一行是一个整数 N (3≤N≤100)，表示村庄的数量。

接下来 N 行，每行包含 N 个整数，在这 N 行中的第 i 行的第 j 个整数 A_ij 表示村庄 i 到村庄 j 建立道路的费用 (1≤A_ij≤1000)。

然后有一个整数 Q (0≤Q≤N×(N+1)/2)。

接下来再 Q 行，每一行包含两个整数 a 和 b (1≤a<b≤N)，即村庄 a 和 b 之间已经建成道路。

输出格式

你应该输出一行包含一个整数，表示所有村庄都连接所要建设道路的最小费用。

样例输入 #1

3
0 990 692
990 0 179
692 179 0
1
1 2

样例输出 #1

179

数据范围

3≤N≤100，1≤A_ij≤1000（对角线为 0），0≤Q≤N×(N+1)/2，1≤a<b≤N。

知识点与难度

本题涉及的知识点：并查集、最小生成树，难度等级：入门。

测试点分布