whix

未归档

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 数论(37) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

全部文章 / 未归档（共32篇）

并查集

1.普通并查集用于记录节点之间的连接关系，使得相互连通关系的点可以用他们共同的父节点来表示。对于父节点不同的点可以通过父节点的合并来改成相互连通。主要用于判断图的连通性（如kruskal算法中）。 int find(int x) { if(x!=pre[x])//包括路径压缩 ...

2019-07-14

0 433

HDU3371题解

此题为最小生成树的基础题，一开始用Prim算法发现超时，当时想的是把已联通的城市当作一个城市，但发现用了太多的时间去处理。最后发现适合用kruskal求解，利用并查集的思想，对于n个点，全部连通需要ee=n-1条边，对于那些已联通的点，输入时进行处理，把他们并起来，使得在使用kruskal算法进行处...

2019-07-14

0 557