D - Constructing Roads

题目链接：

题目：

有N个村庄，编号从1到N，你应该建造一些道路，使每两个村庄可以相互连接。我们说两个村A和B是相连的，当且仅当A和B之间有一条道路，或者存在一个村C以便在A和C之间有一条道路，并且C和B相连。

    我们知道一些村庄之间已经有一些道路，你的工作就是修建一些道路，使所有村庄都连通起来，所有道路的长度都是最小的。

输入

    第一行是整数N（3 <= N <= 100），这是村庄的数量。然后是N行，其中第i个包含N个整数，这些N个整数中的第j个是村庄i和村庄j之间的距离（距离应该是[1,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

思路：只要求最小生成树就行，运用到并查集，详解

//// Created by hy on 2019/7/30.//#include
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include
           
            using namespace std;typedef long long ll;const int maxn=2e5+10;int father[maxn];struct Node{ int u,v,w; bool operator<(const Node &other)const{ return this->w
           
          
         
        
       
      
     

 

见注释