Harris-H

生成树

BFS(5) CF题解(3) DFS(20) DP(20) LCA(2) Leetcode(1) Nowcoder题解(4) ST(1) Tarjan(1) 二分(4) 二分法(1) 二叉树题目(4) 位运算(2) 前缀和(4) 博弈论(3) 图论(1) 字符串(5) 学习笔记(1) 并查集(2) 快速幂(1) 思维(7) 排序(1) 数状数组(3) 数论(20) 暴力(5) 最短路(5) 未归档(5) 标记处理(1) 栈(1) 概率论(1) 模拟(2) 浮点数(1) 算法(5) 素数筛(3) 线段树(6) 组合数学(8) 蓝桥杯(1) 计算几何(1) 贪心(26) 递推(3) 题解(3) 高精度(2)

/ 注册

全部文章 / 生成树（共4篇）

I - Swordfish(最小生成树）

I - Swordfish(最小生成树）题意：给定个点的坐标，求最小生成树。思路：因为最大只有100，用或者都可以。这里重新温习一下两个算法：对所有边排序，每次取最小边，取条边，同时用并查集维护当前图点的集合，如果不在集合里则加入该边。时间复杂度:为边数。用一个数组维护当前子图与所有结...

最小生成树

2020-05-20

1 728

K - Constructing Roads （最小生成树&prim）

K - Constructing Roads （最小生成树&prim）思路：板子题改了一点，给出所有结点的距离和若干个已经建好的道路（即花费为0），求最小生成树。显然prim解决。 AC代码： #include<cstdio> #include<cstring>...

2020-05-01

0 526

J - Building a Space Station （最小生成树&kruskal）

J - Building a Space Station （最小生成树&kruskal）思路：将所有两两的点的距离进行排序,然后用kruskal板子就行，唯一需要注意的是距离为负数不用加。 AC代码：ps(C++ac，G++wa) #include<cstdio> #in...

2020-05-01

0 564

H - Truck History （最小生成树&Prim）

H - Truck History （最小生成树&Prim）题意：给定n个字符串，任意两字符串直接的距离为相同位置不同字符的个数。求生成n个字符串所需要最小的权值和。思路：显然是最小生成树问题，只是距离转化一下。n个字符串看成n个结点，任选一个结点进行prim算法即可。 AC代码...

2020-05-01

0 567