图论 | 最小生成树Kruskal算法（模板）
Kruskal算法是最小生成树两大算法之一，它的核心思想是以边为主导地位，选取所有边里面最小权值的边，但此边不能让已有的边产生回路。最终形成包括了所有（或部分）顶点的权值和最小的生成树。
第一步：按照边权值从小到大，给所有的边排序。（建立边的结构体，包括起点start，终点to，权值val。定义cmp函数，按照边权值从小到大排序）。
第二步：初始化并查集数组，把每个顶点的根节点设为自己。
第三步：从小到大遍历每条边，每到一条边时，并查集数组调用Find函数，判断边的顶点的根节点是否相同（Find函数输入x，返回x的根节点）。
如果根节点不同，就选择这条边，将这条边的权值加到ans，然后继续遍历下一条。如果根节点相同，就跳过不选，不然会形成闭合回路。终止循环的条件是total=n-1。
需要强调的一点是，在对边进行遍历时，合并的是其端点（start，to），而非边本身，记录的total也是在并查集内的顶点数量。
模板题：POJ_1287_Networking
You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you are given the length of the cable that is needed to connect the points over that route. Note that there may exist many possible routes between two given points. It is assumed that the given possible routes connect (directly or indirectly) each two points in the area.
Your task is to design the network for the area, so that there is a connection (direct or indirect) between every two points (i.e., all the points are interconnected, but not necessarily by a direct cable), and that the total length of the used cable is minimal.
Input
The input file consists of a number of data sets. Each data set defines one required network. The first line of the set contains two integers: the first defines the number P of the given points, and the second the number R of given routes between the points. The following R lines define the given routes between the points, each giving three integer numbers: the first two numbers identify the points, and the third gives the length of the route. The numbers are separated with white spaces. A data set giving only one number P=0 denotes the end of the input. The data sets are separated with an empty line.
The maximal number of points is 50. The maximal length of a given route is 100. The number of possible routes is unlimited. The nodes are identified with integers between 1 and P (inclusive). The routes between two points i and j may be given as i j or as j i.
Output
For each data set, print one number on a separate line that gives the total length of the cable used for the entire designed network.
Sample Input
1 0
2 3
1 2 37
2 1 17
1 2 68
3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32
5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12
0
Sample Output
0
17
16
26
AC代码：
using namespace std;typedef long long ll;const int maxn = 200 + 5; //对应顶点数目const int maxm = 1e5 + 5; //对应边的数目int n,m; //n是顶点数量，m是边的数量int start_gen,to_gen; //起始点的根节点,终止点的根节点int f[maxn]; //并查集数组，f[i]指i的根节点struct node{int start; //起始点int to; //终止点int val; //权值}bian[maxm]; //对于边的结构体数组bool cmp(node a,node b){return a.val < b.val;}int Find(int x){ //找x的根节点的Find函数if( f[x] == x ){ //如果自己是根节点，就返回根节点return x;}else{return f[x] = Find(f[x]); //否则就继续找根节点直到找到为止}}int main(){while( cin>>n && n ){ //输入顶点个数for(int i=1;i<=n;i++){ //并查集数组的初始化，每个点祖先为自己f[i] = i;}cin>>m; //输入边的条数for(int i=1;i<=m;i++){ //输入各条边的信息cin>>bian[i].start>>bian[i].to>>bian[i].val;}sort(bian+1,bian+m+1,cmp); //排序ll ans = 0; //权值总和int total = 0; //并查集内边数总和for(int i=1;i<=m;i++){ //对已经排好序的每条边进行循环start_gen = Find(bian[i].start); //找起始点的根节点to_gen = Find(bian[i].to); //找终止点的根节点if( start_gen == to_gen ){ //如果起始点和终止点根节点一致continue; //就继续看下一条边}ans += bian[i].val; //否则，把这条边的权值加到总权值ansf[start_gen] = to_gen; //把新边起点的根节点并入它终点的根节点total++; //有效边数量加1if( total == n - 1 ){ //边的条数到顶点数减1时结束break;}}cout<<ans<<endl;}return 0;}
kuangbin专题里最小生成树例题：
POJ 1251 Jungle Roads
POJ 1287 Networking
POJ 2031 Building a Space Station
POJ 2421 Constructing Roads
ZOJ 1586 QS Network
POJ 1789 Truck History
POJ 2349 Arctic Network
POJ 1751 Highways
POJ 1258 Agri-Net
POJ 3026 Borg Maze
POJ 1679 The Unique MST
HDU 1233 还是畅通工程
HDU 1301 Jungle Roads
HDU 1875 畅通工程再续