Constructing Roads

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 19884		Accepted: 8315

Description

There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.

We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.

Input

The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.

Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.

Output

You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.

Sample Input

30 990 692990 0 179692 179 011 2

Sample Output

179  题目分析： 输入n个村庄，再输入一个邻接矩阵表示点到点的距离，再输入m条边，表示这m条边已经连接，不用考虑路径长度了，求如果想把所有的点都连接  还需要最短再修多长？ 算法分析：此题目和标准的模板有所差别，题目输入是一个二维邻接矩阵的值，然后在输入m条已经联通的边，也就是说这些边已经连接好了，这些 边长就不要计算了。用Kruskal算法，并查集不仅要初始化，还要对这些边进行关联处理，建立父子关系。 代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;struct node{    int u;    int v;    int w;    bool operator <(const node&x)const  //node类自己的运算符重载，这样在sort时，直接写就可以了，不用调用函数了    {        return w
        
       
      
     

  这是从《数据结构 编程实验》那本书上看到的代码：用java写的，感觉并查集用的不错，但是在找边的时候的三层循环实在是不太好，时间性能太差，又很有没必要的循环

  改写成结构体数组还是比较好使的。

 代码如下：

 

import java.util.*;import java.io.Reader;import java.io.Writer;import java.math.*; //导入java下的工具包public class Main{	public static void print(string x){  //输出最小生成树的边长和		System.out.print(x);	}	static int[] fa; //并查集数组	public static int findset(int x){		return fa[x]!=x?fa[x]=findset(fa[x]):x; 	} //带压缩路径的并查集	public static void main(string[] argv){ //定义main函数的参数是一个字符串类型的数组argv		Scanner input = new Scanner(System.in); //定义java的标准输入		while(input.hasNextInt() ){ //多组测试			int N = input.nextInt();			int [][]p = new int [N+1][N+1]; //为邻接矩阵申请内存			for(int i=0; i
     
      0; m-- )			{				fa[findset(input.nextInt()-1)] = findset(input.nextInt()-1); //建立父子关系			}			int ans=0; //新建公路的长度初始化			for(int k=1; k<=1000; k++)			{				for(int i=0; i