iiiiikun
iiiiikun
全部文章
最小生成树
bfs(11)
codeforce(2)
codeforces(49)
dfs(27)
dp(65)
icpc(2)
kmp(2)
kruskal(1)
min25(1)
spfa(3)
stl(3)
三分(1)
二分(11)
二分图(3)
二叉树(2)
二叉树遍历(1)
倍增(1)
几何(1)
前缀和(6)
剪枝(1)
动态规划(2)
单调栈(1)
博弈论(1)
双指针算法(1)
双端队列(1)
唯一分解定理(1)
回文(1)
图论(4)
堆(1)
字符串(2)
尺取法(1)
差分(4)
差分约束(1)
并查集(7)
循环节(1)
快速幂(3)
思维(5)
思维题(6)
拓扑排序(2)
排序(1)
数位dp(3)
数位交换(1)
数学题(1)
数据结构(7)
数论(17)
最大子矩阵(2)
最短路(17)
最长公共上升子序列(1)
有向图强联通分量(4)
未归档(8)
权值线段树(2)
构造(2)
枚举(2)
栈(1)
树形dp(4)
树状数组(3)
树的直径(1)
概率(1)
模拟(1)
模拟赛(1)
模拟退火(1)
模板(9)
欧几里得(1)
欧拉回路欧拉路径(1)
牛客多校(1)
状态压缩(1)
矩形面积(1)
矩阵乘法(1)
矩阵快速幂(1)
离散化(1)
筛素数(1)
线段树(4)
网络流(3)
背包(1)
菜鸟(14)
蓝桥(23)
蓝桥杯(2)
蓝桥训练(2)
贪心(11)
递归(1)
递推(2)
链表(2)
队列(3)
题解(2)
马拉车(2)
高精度(1)
归档
标签
去牛客网
登录
/
注册
iiiiikun的博客
老废物了
全部文章
/ 最小生成树
(共8篇)
kruskal求最小生成树
思路:先按照每条边的权值排序,从小到大枚举每条边,如果这条边两个顶点的祖宗节点不一样,连接上这条边并且计数器加一,最后如果计数器小于顶点个数-1的话,就说明不到n个点,就不可能,否则输出答案 代码如下: #include<iostream> using namespace std; c...
2020-12-17
0
455
最小生成树 acwing1146. 新的开始
发展采矿业当然首先得有矿井,小 FF 花了上次探险获得的千分之一的财富请人在岛上挖了 n口矿井,但他似乎忘记了考虑矿井供电问题。 为了保证电力的供应,小 FF 想到了两种办法: 在矿井 i上建立一个发电站,费用为 vi (发电站的输出功率可以供给任意多个矿井)。 将这口矿井 i与另外的已经有...
2020-12-17
0
600
蓝桥训练最小生成树kruscal
栋栋居住在一个繁华的C市中,然而,这个城市的道路大都年久失修。市长准备重新修一些路以方便市民,于是找到了栋栋,希望栋栋能帮助他。 C市中有n个比较重要的地点,市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点,每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过,也可以在其...
2020-12-17
0
477
最小生成树(士兵招募)
Windy has a country, and he wants to build an army to protect his country. He has picked up N girls and M boys and wants to collect them to be his sol...
2020-12-17
0
407
1143, 联络员
解题报告:应该把要选的都给选上,然后在从小到大选边。 #include<bits/stdc++.h> const int N=31000; using namespace std; struct node{ int p; int a; int b; ...
2020-12-17
0
431
1145. 北极通讯网络
网站 解题报告:这道题实质上是在问满足存在k个连通块的最小d是多少。然而并不用二分,因为在kruskal算法的过程中本身联通块的数目就是递减的,从一开始的n到k然后记录最小值就能ac这道题了。 #include<iostream> #include<cstring> #i...
2020-12-17
0
527
AcWing 346. 走廊泼水节
解题报告:这题一开始没看懂,其实意思挺简单的,当然是看了题解以后 还挺容易的,主要是让你把一个树形图,变成一个完全图,(完全图就是边长数量=(n*(n-1)/2)n为点数),同时满足之前的那棵树还是唯一的最小生成树,通过图我们可以发现,在合并两个集合的时候,如果枚举的边小于等于该条边的长度w,是不行...
2020-12-17
0
384
次小生成树
**解题报告:**这还是个定理吧,就是说我们可以删掉最小生成树的一条树边,然后加上该点的树边,就能形成一个生成树,(如上图p2,绿色的边是两个点之间的最长树边,我们可以把他删掉,加上蓝色的边,这样并不影响它的连通性,所以他还是生成树)那么就一定有他的值是sum-l+w,为了让这个值最小并且比sum大...
2020-12-17
0
477