基本思想：（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中所有顶点都在同一连通分量上为止。
模板题1
百练 Tangled in Cables
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
- You are the owner of SmallCableCo and have purchased the franchise rights for a small town. Unfortunately, you lack enough funds to start your business properly and are relying on parts you have found in an old warehouse you bought. Among your finds is a single spool of cable and a lot of connectors. You want to figure out whether you have enough cable to connect every house in town. You have a map of town with the distances for all the paths you may use to run your cable between the houses. You want to calculate the shortest length of cable you must have to connect all of the houses together.
- 输入
- Only one town will be given in an input.
- The first line gives the length of cable on the spool as a real number.
- The second line contains the number of houses, N
- The next N lines give the name of each house's owner. Each name consists of up to 20 characters {a–z,A–Z,0–9} and contains no whitespace or punctuation.
- Next line: M, number of paths between houses
- next M lines in the form
< house name A > < house name B > < distance >
Where the two house names match two different names in the list above and the distance is a positive real number. There will not be two paths between the same pair of houses. - 输出
- The output will consist of a single line. If there is not enough cable to connect all of the houses in the town, output
Not enough cable
If there is enough cable, then output
Need < X > miles of cable
Print X to the nearest tenth of a mile (0.1). - 样例输入
-
123456789101112100.04JonesSmithsHowardsWangs5Jones Smiths 2.0Jones Howards 4.2Jones Wangs 6.7Howards Wangs 4.0Smiths Wangs 10.0
- 样例输出
-
1Need 10.2 miles of cable
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 60 61 62 63 |
#include<iostream> #include<vector> #include<unordered_map> #include<algorithm> #include<cstdio> using namespace std; double cableLen = 0; int n, m; int father[501]; struct node{ string src; string dst; double val; }; int findFather(int x){ while(x != father[x])x = father[x]; return x; } bool unionSet(int x, int y){ int fx = findFather(x); int fy = findFather(y); if(fx != fy){ father[fy] = fx; return true; } return false; } bool cmp(node a, node b){return a.val < b.val;} int main(){ double anslen = 0; int k = 0, i = 0; scanf("%lf%d", &cableLen, &n); unordered_map<string, int> name; for(int i = 0; i < n; i++){ string str; cin>>str; father[i] = i; name[str] = i; } scanf("%d", &m); 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); while(k < n - 1){ if(unionSet(name[pool[i].src], name[pool[i].dst])){ anslen += pool[i].val; k++; } i++; } if(anslen <= cableLen) printf("Need %.1f miles of cable\n", anslen); else printf("%s\n", "Not enough cable"); return 0; } |
