【学习笔记】基础算法——生成树
最小生成树应该都知道最小生成树是什么吧。
不知道的左转先理解最小生成树的定义！
好的上例题！
水。
两种做法，一个是 K 啥的，还有一个是 Prim 吧。
K 算法
时间复杂度 \(O(m\log m)\)，瓶颈在于排序。
非常常用！代码很短！但是适用于稀疏图。
代码不贴了。
P 算法
时间复杂度应该是 \(O(n^2)\) 吧。
K 算法是加边，而 P 算法是加点。
很简单。适用于稠密图。但是并不很常用，因为一般 K 算法都是首选。
最小生成树的运用
我问你呢，有多少个题目会在脑袋上写着大大的“最小生成树”五个大字？不，不可能。都是藏着掖着的！
把“最小生成树”的提示藏在字里行间，需要你仔细剖析题目意思，详细分析题目要求才能发现。
运用很巧妙哇！
直说不好说啊。看几个题吧。
例题——Dungeons and Candies
乍一看，你看得出来这是最小生成树？不，当然看不出来。
它是藏着的！你需要去剖析，它的这个结构确实是一个树的形态，然后整个你需要自己去枚举，去连边，去造生成树。最后输出的时候还得遍历！
还是有难度的。
来，看一下代码：
#include#define LL long longusing namespace std;const int N = 1e3+5 , M = 2e6+5;struct line{int u,v,w;}ln;vector g;char c;int n,m,k,w,fa,cnt,ans,sum;bool cmp(line l1,line l2){return l1.w
页:
[1]