基本思想：（1）构造一个只含n个顶点，边集为空的子图。若将图中各个顶点看成一棵树的根节点，则它是一个含有n棵树的森林。（2）从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图。也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之（3）依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
大白话：（1）将图中的所有边都去掉。（2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环（3）重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。
难点：判断某条边<u, v>的加入是否会在已经选定的边集集合中形成环。
解决办法：使用并查集，分别找出两个顶点u, v所在树的根节点。若根节点相同，说明u, v在同一棵树中，则u, v连接起来会形成环；若根节点不同，则u, v不在一棵树中，连接起来不会形成环，而是将两棵树合并。
克鲁斯卡尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。
百练1287 Networking
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- 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. - 输入
- 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. - 输出
- 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.
- 样例输入
-
12345678910111213141516171819202122232425261 02 31 2 372 1 171 2 683 71 2 192 3 113 1 71 3 52 3 893 1 911 2 325 71 2 52 3 72 4 84 5 113 5 101 5 64 2 120
- 样例输出
-
12340171626
C++实现（AC）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<algorithm> #include<vector> using namespace std; //Kruskal最小生成树模板题 int n, m, father[100000]; struct node{ int src, dst; int val; }; bool cmp(node a, node b){return a.val < b.val;} int findFather(int a){ int t = a; while(a != father[a])a = father[a]; //找到根节点 return a; } void init(){ for(int i = 1; i <= n; i++)father[i] = i; } int unionSet(int x, int y){ //和并查集一样，如果将根合并 int fx = findFather(x); int fy = findFather(y); if(fx != fy){ father[fx] = fy; return 1; }return 0; } int main(){ while(cin>>n){ if(n == 0)break; init(); //初始化不能丢 cin>>m; int ans = 0; vector<node> pool(m); for(int i = 0; i < m; i++){ cin>>pool[i].src>>pool[i].dst>>pool[i].val; } sort(pool.begin(), pool.end(), cmp); int k = 0, i = 0; while(k < n - 1){ if(unionSet(pool[i].src, pool[i].dst)){ //如果两个节点的根不一样则合并，本质上将两个预给定的边选择出来 //也不会成环 k++; ans += pool[i].val; } i++; } cout<<ans<<endl; } return 0; } |
相关
