问题2096--道路建设

2096: 道路建设

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 8
[提交] [状态] [讨论版] [命题人:]

题目描述

有N 个村庄，编号为1～N ，需要建造一些道路，使每两个村庄之间都可以相互连接。两个村庄A和B是相连的，当且仅当A和B之间有一条道路，或者存在一个村庄C，A和C相连且C和B相连。已知一些村庄之间已经有一些道路，你的工作是修建一些道路，使所有村庄都连通起来，所有道路的长度之和最小。

输入

第1行是整数N （3≤N ≤100），表示村庄的数量；然后是N 行，其中第i 行包含N 个整数，第j 个整数表示村庄i 和村庄j之间的距离（距离为[1,1000]内的整数）；接着是整数Q （0≤Q ≤N×(N +1)/ 2），表示已建成道路的数量；最后是Q 行，每行都包含两个整数a 和b （1≤a <b ≤N ），表示村庄a 和村庄b 之间的道路已经建成。

输出

单行输出需要构建的所有道路的最小长度。

样例输入 Copy 

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

样例输出 Copy 

179

来源/分类

最小生成树 Prim算法 Kruskal算法 
[提交] [状态]