Iridescent41
Iridescent41
全部文章
未归档
归档
标签
去牛客网
登录
/
注册
ChenJG41
Never Give Up
全部文章
/ 未归档
(共6篇)
最小生成树 学习笔记1 - Kruskal
最小生成树 定义 Kruskal算法 算法流程 具体实现 建立结构体存边 并查集维护 完整代码 定义 给定一个带权图,满足以下条件: 1.保证图中所有的点都联通 2...
最小生成树
2020-08-05
0
229
SCOI 滑雪与时间胶囊 题解
SCOI 滑雪与时间胶囊 题目描述 a180285 非常喜欢滑雪。 他来到一座雪山,这里分布着\(M\)条供滑行的轨道和\(N\)个轨道之间的交点(同时也是景点),而且每个景点都有一编号\(i(1<=i<=n)\)和一高度$$。a180285 能从景点\(i\)滑到景点\(j\)当且...
最小生成树
2020-08-15
0
247
构造完全图 题解
题目链接 分析 假设有如下图两个集合 \(x\) & \(y\)。因为要构造一个完全图,所以应该将\(x\)中的\(s[x]\)个节点与\(y\)中的\(s[y]\)个节点一一连接即连接\(s[x] * s[y] - 1\)(此处减一是为了在后面单独处理原图中的\(dis[i].w\))...
最小生成树
2020-08-16
0
297
秘密的牛奶运输 题解
题目连接 分析 一道可以暴力水过去的次小生成树 step1 首先用\(Kruskal\)||\(Prim\)求出原图的一颗最小生成树,在连边的时候,用一个\(vis\)记录一下那些已经在最小生成树里面。 step2 提前暴力\(dfs\)或者\(bfs\)求出...
最小生成树
2020-08-16
0
357
「一本通 3.1 练习 4」Tree 题解
题目地址 分析 第一眼看到此题,感觉就是一道水题,直接加上前\(need\)小的白边就行了,再处理到\(n-1\)条黑边,但是,打完后突然发现有问题。。。 虽然加上了前\(need\)小的白边,但是会出现树不连通的现象,即无法构成生成树。 正解思路 二分一个增量\(mid\)(可正可负)。 ...
最小生成树
2020-08-16
0
286
Star Way To Heaven 题解
题目链接 分析 此题可以暴力二分,但是只有80pts,所以不采纳这个思想。 考虑与最小生成树的关系,当所有的引力把能走的路全部封死之后,此时的\(ans\)便是最大的引力圈的半径。 step1 首先初始化\(dis[i] = m - y[i]\),把dis[k+1]设为m。 step2 ...
最小生成树
2020-08-16
0
238