1985: 道路规划

【问题描述】

有N个村庄,编号从1到N,请你建立一些道路,使得任意两个村庄可以相连。

我们说两个村A和B是相连的,当且仅当有一条公路在A与B之间,或存在一个村庄C,有一条的道路连接着A和C之间,一条连接着B和C。

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

【输入格式】

第一行是一个整数N(3 <= N <= 100),表示村庄的数量。

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

然后有一个整数Q(0 <= Q <= N *(N + 1)/2)。接下来再Q行,每一行包含两个整数a和b(1 <= a < b <= N),即村庄a和b之间已经建成道路。

【输出格式】

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

【输入样例】

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

【输出样例】

第一行是一个整数N(3 <= N <= 100),表示村庄的数量。

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

然后有一个整数Q(0 <= Q <= N *(N + 1)/2)。接下来再Q行,每一行包含两个整数a和b(1 <= a < b <= N),即村庄a和b之间已经建成道路。

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

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

179