D - Constructing Roads
题目链接：https://vjudge.net/contest/66965#problem/D
题目：
有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<algorithm> #include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <set> #include<math.h> 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<other.w; } }node[maxn]; int find(int x) { if(x==father[x]) return x; return father[x]=find(father[x]); } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) father[i]=i; int m=0; int t; for(int i=1;i<=n;i++) { for (int j = 1; j <= n; j++) { scanf("%d", &t); node[m].u = i; node[m].v = j; node[m++].w = t; } }//加权值 sort(node,node+m);//排序m条边 int q; scanf("%d",&q); int x,y; for(int i=1;i<=q;i++) { scanf("%d%d",&x,&y); int xx=find(x); int yy=find(y); if(xx==yy) continue; else father[xx]=yy;//如果输入的不连通，则合并 } int ans=0; for(int i=1;i<=m;i++) { int aa=find(node[i].u); int bb=find(node[i].v); if(aa!=bb) { ans+=node[i].w; father[aa]=bb; }//找每条路，如果不连通，则累加权值，并合并起来 } printf("%d ",ans); return 0; }
见注释