P1195 – 口袋的天空
题目 题目链接 链接 题目大意 给你n个点，m条边，要生成k个最小生成树 题解 刚开始想的就是kruskal，但是没理解串成k串棉花糖。也就是至少生成k个最小生成树。 生成一个n个点的树需要n-1条边，然后生成k个最小生成树那就至少需要n-k条边。 所以我们如…
Tag: 最小生成树
Kruskal
kruskal int n, m; // n是点数，m是边数 int p[N]; // 并查集的父节点数组 struct Edge // 存储边 { int a, b, w; bool operator< (const Edge &W)const…
Prime
prime 模板 /* S:当前已经在联通块中的所有点的集合 1. dist[i] = inf 2. for n 次 t<-S外离S最近的点 利用t更新S外点到S的距离 st[t] = true n次迭代之后所有点都已加入到S中 联系：Dijkstra算…