最小生成树专题

+ ### P3367 【模板】并查集 并查集模版。 + ### P1111 修复公路 如果公路两端点祖先不同，说明可以合并这两棵树，什么时候剩余树的数量为 $ 1 $ 即为任意两地均可通车。 + ### P2256 一中校运会之百米跑 用 ``` map ``` 建立字符串和数字间的映射关系，将字符串用数字代替后就是简单地并查集操作了。 + ### P1551 亲戚 由题意得，只要两人在一棵树上就是亲戚关系。 + ### P1621 集合 先筛质数，筛完枚举这个质数（$ x $）在 $ a $ 到 $ b $ 间的倍数，执行 ``` to[find(x + prim[i])] = find(x)```。 + ### P1682 过家家 将所有女孩子间是朋友关系的合并到一颗树上，随后用 ``` play[][] ``` 数组标记一个女孩子所在的连通块（``` find(ok[i].first) ```）和一个男孩子（``` ok[i].second ```）可以一起玩，于是标记 ``` play[find(ok[i].first)][ok[i].second] = 1```，即他们可以一起玩，并将这个连通块中玩伴数量（``` num[find(ok[i].second] ```）$ + 1$。又因为一个女孩子可以强制和 $ k $ 个男孩子玩耍，所以将 ``` num[] ``` 数组中不为 $ 0 $ 的位置（说明是根节点）取最小值后 $ + k$，再跟 $ n $ 取最小值（两个人之间最多只能玩一次，因此最多只能玩 $ n $ 轮）并输出。 + ### P2391 白雪皑皑 倒序操作，用并查集或链表优化寻找没有染色的雪花的过程。 + ### P3366 【模板】最小生成树 最小生成树模板。 + ### P1195 口袋的天空 要连成 $ k $ 朵棉花糖，也就是 $ k $ 个联通的块，为了使费用最小，我们就不能让其中出现回路，即需要连成 $ k $ 棵树，也就是需要选出 $ n - k $ 条边。 + ### P1194 买礼物 将能优惠的物品建边，不能优惠的不建边，注意只用建一半（``` i < j ```）。最后从 $ 0 $ 号点往 $ 1 $ 到 $ b $ 号点分别建一条长度为 $ a $ 的边，代表不优惠的情况（因为想要凑优惠一定需要买一个原价的物品），跑一遍 ``` Kruskal ``` 算法即可。 + ### P1265 公路修建 由题意得，第二种情况不存在，因此我们需要求出一棵最小生成树。但 ``` Kruskal ``` 算法需要存下每条边，空间复杂度过高，而且排序的时间复杂度也过高；``` Prim``` 的小根堆优化版本也是如此。因此我们选择 ``` Prim ``` 的暴力版本进行求解。 + ### P1340 兽径管理 如果真的在读入每一组新的兽径后都进行一次排序 + ``` Kruskal ```，显然会超时（``` C++98 + scanf + printf + '\n' ``` 可以卡过）。因此我们可以记录每条兽径的出现时间，在最后进行一次排序，在每次 ``` Kruskal ``` 的过程中判断这条兽径此时有没有被发现即可。 + ### P1396 营救 求出 $ s $ 到 $ t $ 之间最小拥挤度的路线，我们可以借鉴 ``` Kruskal ``` 的思路，将边排序后依次加入生成树，直到 $ s $ 和 $ t $ 联通，此时拥挤度就是最小的。 + ### P1550 [USACO08OCT] Watering Hole G 由题意得，无论如何我们都需要水，因此可以设置一个 $ 0 $ 号点当做水源，再将 ``` i != j ``` 的点之间建边，注意只用建一半（``` i < j ```），最后跑一遍 ``` Kruskal ``` 即可。 + ### P1536 村村通 每次读入一条新的公路，就判断加入并查集能否使新的两个点联通，如果可以就将 ``` ans++ ```，最后输出 $ n - 1 - ans $（$ n $ 个点互相连通需要至少 $ n - 1 $ 条公路，我们每次都让没有联通的点联通，因此直接输出 $ n - 1 - ans $ 即可）。 + ### P1546 [USACO3.1] 最短网络 Agri-Net 要连接所有农场并使费用最小，就是求出一棵最小生成树，注意建边只用建一半（``` i < j ```）即可。 + ### CF916C Jamie and Interesting Graph 首先，最多会有 $ 10 ^ 5 $ 个点，最小生成树和最短路都需要有 $ 99999 $ 条边，因此我们需要选择的质数一定大于 $ 99999$，这里我选择了 $ 100003$。我们可以将构建最小生成树和最短路的树形结构化为链式结构，将 $ 1 \to 2 $ 的边权设为 $ 100003 - (n - 2)$（$ 100003 $ 是答案总边权，剩下的 $ n - 2 $ 条边边权可以都是 $ 1$）。然后为了弥补剩余的边，我们枚举双重循环（$ i : 1 \to n , j : 1 \to i$），判断边是否之前出现过（这里因为满足 $ i >= j$，因此不用考虑 $ i \to j $ 和 $ j \to i $ 的重边情况，因此只用判 ``` i != j && i != j + 1 ``` 即可），并将这些边的边权都设置为大于 $ 100003 $ 的数（$ 100004 $ 即可）。 + ### P3073 [USACO13FEB] Tractor S 我们可以把每个点 $ (x , y) $ 用 $ (x - 1) * n + y $ 来表示在一维下这个点的编号，以此保证并查集仍然是一维的。随后我们可以从一个顶点出发，向周围能到达的点建边，边权是两点的点权之差的绝对值。由题意得，我们需要求得的是一个大小 ``` >= ceil(n * n * 1.0 / 2) ``` 的连通块，可以在维护最小生成树和并查集基础上多维护一个 ``` size[] ``` 数组当做连通块大小。注意要先更新 ``` size[] ``` 数组的值再合并并查集，否则两个点祖先相同会导致答案错误。我们也可以只建向右和向下的边，也可以起到联通全图的效果，而且这样省空间也更快。 + ### P4047 [JSOI2010] 部落划分 虽然本题题面较长，但是仔细思考就会发现：一个部落可以当做一个点；两个部落之间的距离就是两点之间的距离；划分为 $ k $ 个部落就是连出 $ k $ 个连通块。这让我们想到了最小生成树。但又因为要求出相邻两部落最短距离，其实就是 Kruskal 算法求完最小生成树之后最短的不在同一并查集的边权（如果这条边不是最短的，那么一定在这之前有一条更短的边，那么在遍历存边的数组时，一定会先遍历到这之前的那条边，但现在没有，因此这条边最短）。 + ### P4180 [BJWC2010] 严格次小生成树 严格次小生成树模板。