vlambda博客
学习文章列表

        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代码：

#include<iostream>#include<cstdio>#include<algorithm>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; //否则，把这条边的权值加到总权值ans f[start_gen] = to_gen; //把新边起点的根节点并入它终点的根节点 total++; //有效边数量加1 if( 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  畅通工程再续