搜索结果
查询Tags标签： 连通，共有 112条记录-
状态压缩-1595. 连通两组点的最小成本
问题描述 给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。 任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一…
2022/9/16 23:18:21 人评论 次浏览 -
AcWing算法提高课 最小生成树
一般使用kruskal(克鲁斯卡尔)(mlogm) 对于稀疏图，用朴素prim(n^2) prim:每次选择和当前已经构建出的连通块相连，且权重最小的边，加入当前连通块。 一共需要扩展(n-1)次 kruskal:基于并查集。先将所有边从小到大排序，然后枚举每条边，如果边的两个端点还不联通，则将当…
2022/9/14 1:19:09 人评论 次浏览 -
题解 洛谷 P3915 【树的分解】
1## P3915 树的分解 题目描述给出\(N\)个点的树和K，问能否把树划分成\(\frac{N}{K}\)个连通块，且每个连通块的点数都是\(K\)。 解题思路 分析样例： 「\(sample1\)」可被划分为\(1\).\(2\)、\(3\).\(4\)两个大小为\(2\)的连通块。 「\(sample2\)」无法被划分为大小为\(2…
2022/9/10 6:23:11 人评论 次浏览 -
最小生成树
专门开个博客一是因为没地放了，二是以后次小生成树什么的就一块扔这了。 点数n，边数m的图的最小生成树大概有两个算法：Kruskal算法(\(O(m\log m)\))思路非常简单粗暴，把所有边扔出来按照边权排个序，然后拿并查集维护点的连通关系，最后选出n-1条边。 int kruskal(int…
2022/9/3 23:22:56 人评论 次浏览 -
欧拉路径学习笔记
\(\bigstar\) 欧拉路径 若 \(G=(V,\ E)\) 中的一条路径包含了 \(E\) 中的所有边且不重复，则称其为 欧拉路径（\(\textbf{Eulerian Path}\)）。 若该路径的起点与终点相同，则称其为 欧拉回路（\(\textbf{Eulerian Circuit}\)）。 欧拉路径的存在条件：此图连通；对于无向…
2022/8/15 6:26:39 人评论 次浏览 -
CF 1600~1800 思维题泛做
CF 1592C Bakry and Partitioning给定一棵 \(n\) 个节点，每个节点有点权的树，最多拆成 \(k\) 个连通块，问是否有方案使得所有联通块的异或和相等。 \(n,k \le 10^5,a_i \le 10^9\)\(\color{Blue}{1700}\) 对于异或，存在重要性质 \(x\, \text{xor}\, x = 0\)。 设所有数…
2022/8/13 23:29:13 人评论 次浏览 -
1175. 最大半连通子图
题目链接 1175. 最大半连通子图 一个有向图 \(G = (V,E)\) 称为半连通的 (Semi-Connected)，如果满足：\(\forall u,v \in V\)，满足 \(u \to v\) 或 \(v \to u\)，即对于图中任意两点 \(u,v\)，存在一条 \(u\) 到 \(v\) 的有向路径或者从 \(v\) 到 \(u\) 的有向路径。 若…
2022/8/11 23:24:41 人评论 次浏览 -
洛谷 P6668 - [清华集训2016] 连通子树（虚树+点分治）
洛谷题面传送门 一道思维难度为 \(<\epsilon\) 的题。 首先先考虑单组询问的情况。有个究极暴力的做法，\(dp_{i,x,y,z}\) 表示 \(i\) 子树内三种颜色个数分别为 \(x,y,z\) 的连通块个数，转移相当于合并两个连通块，只能 \(O((na+1)^2(nb+1)^2(nc+1)^2)\) 地进行，因此…
2022/8/11 6:27:09 人评论 次浏览 -
ZZULI (2022河南萌新联赛 四)
题目描述分析 读题不认真这个毛病什么时候能改? 我竟然看成最长上升子序列问题了, 而且还把代码写好.......(其实就算看出来是并查集, 我也不会写qwq)赛后借鉴大佬代码, 收获很大 以后看到连通块这个词, 就往并查集的方向想 AC代码 #include <iostream> #include &…
2022/7/31 23:43:50 人评论 次浏览 -
LG6144 [USACO20FEB]Help Yourself P【DP，组合数，线段树】
传送门 思路 考虑 DP，设 \(f_{i,j,k}\) 表示前 \(i\) 条线段，连通块最右端的点为 \(j\) 的所有子集的连通块个数的 \(k\) 次方之和。初值 \(f_{0,0,0} = 1\)，答案为 \(\sum f_{n,j,K}\)。 把线段按照左端点排序，考虑加入第 \(i\) 条线段后对答案的影响，设 \(j\) 为加…
2022/7/23 23:24:43 人评论 次浏览 -
Boruvka 算法
Boruvka算法解决某些问题超级好用。 这些问题形如，给你n个点，每个点有点权，任意两个点之间有边权，边权为两个点权用过某种计算方式得出。 求最小生成树。 通常用 \(O(log n)\) 的时间可以找到与点i连边的边权最小的j。 我们考虑这样一个求最小生成树的算法： 考虑维护…
2022/6/26 1:20:20 人评论 次浏览 -
【C# 数据结构与算法】 最小生成树
概览 概念 最小生成树是一副连通加权无向图中一棵权值最小的生成树。 在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 ( u , v ) ∈ E {\displaystyle (u,v)\in E} ），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即 T ⊆ E {\disp…
2022/6/10 1:22:25 人评论 次浏览 -
noip模拟26
T1. LCIS 数组开小 100pts->60pts 蓝书原题，决策集合最优化\(O（n^2）\) 我用的树（状数组）套树（装数组） 与 值域优化对冲，导致达不到\(O(n ^ 2 (logn) ^2)\)的复杂度，lyin试图卡掉以失败告终 最坏复杂度\(O(n^2 logn )\),好多人\(O(n^4)\)跑得飞快 T2.物流运输 …
2022/6/7 23:23:00 人评论 次浏览 -
cf550 D. Regular Bridge
题意： 给定 \(k\)，构造连通、无重边、无自环、每个点的度为 \(k\) 且含至少一个桥的无向无权图 \(1\le k \le 100\) 思路： 当 \(k\) 为偶数时无解：设 \(k=2s\)，设某连通块 \(G\) 与图的其他部分通过桥 \(e\) 连接，去掉桥 \(e\)，则 \(G\) 中有一个点的度为 \(2s-1\)…
2022/6/6 23:23:02 人评论 次浏览 -
OOUnit2
OOunit2总结博客 (1)总结分析三次作业中同步块的设置和锁的选择，并分析锁与同步块中处理语句之间的关系 作业中同步块都在共享对象中的方法，共享对象实现如下接口： public interface Queue {void addRequest(Request request);//添加成员void setEnd();//传递结束信号b…
2022/5/3 6:12:56 人评论 次浏览
