响水做网站价格抖音号出售网站

响水做网站价格,抖音号出售网站,高端网站开发哪里有,南京网站建设策划方案并查集 1.1 双亲表⽰法 接下来要学习到的并查集#xff0c;本质上就是⽤双亲表⽰法实现的森林。因此#xff0c;我们先认识⼀下双亲表⽰ 法。 在学习树这个数据结构的时#xff0c;讲到树的存储⽅式有很多种#xff1a;孩⼦表⽰法#xff0c;双亲表⽰法、孩⼦双亲表⽰ 法…并查集1.1双亲表⽰法接下来要学习到的并查集本质上就是⽤双亲表⽰法实现的森林。因此我们先认识⼀下双亲表⽰法。在学习树这个数据结构的时讲到树的存储⽅式有很多种孩⼦表⽰法双亲表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。对⼀棵树⽽⾔除了根节点外其余每个结点⼀定有且仅有⼀个双亲双亲表⽰法就是根据这个特点存储树的也就是把每个结点的双亲存下来。因此我们可以采⽤数组来存储每个结点的⽗亲结点的编号这就实现了双亲表⽰法(so easy)。但是在实现并查集的时我们⼀般让根节点⾃⼰指向⾃⼰。因此上述存储就变成1.2并查集的概念在有些问题中我们需要维护若⼲个集合并且基于这些集合要频繁执⾏下⾯的操作• 查询操作查找元素x属于哪⼀个集合。⼀般会在每个集合中选取⼀个元素作为代表查询的是这个集合中的代表元素• 合并操作将元素x所在的集合与元素y所在的集合合并成⼀个集合注意合并的是元素所在的集合不是这两个元素• 判断操作判断元素x和y是否在同⼀个集合。并查集Union Find是⼀种⽤于维护元素所属集合的数据结构实现为⼀个森林其中每棵树表 ⽰⼀个集合树中的节点表⽰对应集合中的元素根节点来代表整个集合。1.3并查集的实现1.3.1初始化初始状态下所有的元素单独成为⼀个集合• 让元素⾃⼰指向⾃⼰即可。代码实现#include iostream using namespace std; // 定义数组最大容量100万10留余量避免越界 const int N 1e6 10; // n表示需要管理的元素总数 int n; // fa数组fa[i]代表元素i的父节点组长双亲表示法核心数组 int fa[N]; // 初始化并查集函数让每个元素的父节点都是自己自成一组 void init() { // 遍历1到n的所有元素 for(int i 1; i n; i) { // 每个元素初始时组长是自己 fa[i] i; } } // 主函数示例演示如何使用初始化函数 int main() { // 示例假设要管理5个元素 n 5; // 调用初始化函数 init(); // 打印初始化后的fa数组验证结果 cout 初始化后fa数组 endl; for(int i 1; i n; i) { cout fa[ i ] fa[i] endl; } return 0; }1.3.2查询操作查询操作是并查集的核⼼操作其余所有的操作都是基于查询操作实现的找到元素x所属的集合• ⼀直向上找爸爸~代码实现int find(int x) { if(fa[x] x) return x; return find(fa[x]); // 一行实现 // return fa[x] x ? x : find(fa[x]); }1.3.3合并操作将元素x所在的集合与元素y所在的集合合并成⼀个集合• 让元素x所在树的根节点指向元素y所在树的根节点。反过来也是可以的代码实现// 合并操作 void un(int x, int y) // 注意函数名字不能⽤ union因为它是 C 的关键字 { int fx find(x); int fy find(y); fa[fx] fy; }1.3.4判断操作判断元素x和元素y是否在同⼀集合• 看看两者所在树的根节点是否相同。代码实现// 判断是否在同⼀集合 bool issame(int x, int y) { return find(x) find(y); }1.4并查集的优化极端情况在合并的过程中整棵树变成⼀个链表。路径压缩在查询时把被查询的节点到根节点的路径上的所有节点的⽗节点设置为根节点从⽽减 ⼩树的深度。也就是说在向上查询的同时把在路径上的每个节点都直接连接到根上以后查询时 就能直接查询到根节点。代码实现// 找根节点 - 路径压缩 int find(int x) { if(fa[x] x) return x; return fa[x] find(fa[x]); // ⼀⾏实现 return fa[x] x ? x : fa[x] find(fa[x]); }还有⼀种优化⽅式是按秩合并但是基本上不⽤按秩合并并查集的时间复杂度就很优秀了。感兴趣 的同学可以搜⼀下按秩合并按照⼤家现在的⽔平应该很容易就能看懂~在《算法导论》中有严格的证明并查集查询根节点的最坏时间复杂度为O(α(n)) 是⼀个很⼩的常 数。因此并查集查询以及合并的效率近似可以看成O(1)。1.5普通并查集1.5.1【模板】并查集题⽬来源 洛⾕题⽬链接P3367 【模板】并查集难度系数 ★★题目背景本题数据范围已经更新到 1≤N≤2×1051≤M≤106。题目描述如题现在有一个并查集你需要完成合并和查询操作。输入格式第一行包含两个整数 N,M ,表示共有 N 个元素和 M 个操作。接下来 M 行每行包含三个整数 Zi​,Xi​,Yi​ 。当 Zi​1 时将 Xi​ 与 Yi​ 所在的集合合并。当 Zi​2 时输出 Xi​ 与 Yi​ 是否在同一集合内是的输出Y否则输出N。输出格式对于每一个 Zi​2 的操作都有一行输出每行包含一个大写字母为Y或者N。输入输出样例输入 #1复制4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4输出 #1复制N Y N Y说明/提示对于 15% 的数据N≤10M≤20。对于 35% 的数据N≤100M≤103。对于 50% 的数据1≤N≤1041≤M≤2×105。对于 100% 的数据1≤N≤2×1051≤M≤1061≤Xi​,Yi​≤NZi​∈{1,2}。【解法】模板题~【参考代码】#include iostream using namespace std; const int N 2e5 10; // 数组最大容量20万10留余量 int n; // 元素总数比如示例里n4 int fa[N]; // fa[i]元素i的父节点组长 // find函数找元素x的“最终组长”根节点并做路径压缩提速 int find(int x) { // 如果x的父节点是自己说明x就是组长直接返回 if(fa[x] x) return x; // 否则递归找x父节点的组长同时把x的父节点直接指向组长路径压缩 return fa[x] find(fa[x]); } int main() { int T; // T是操作总数示例里T7 cin n T; // 初始化并查集每个元素的组长都是自己 for(int i 1; i n; i) fa[i] i; // 遍历所有操作T--执行T次每次减1 while(T--) { int z, x, y; // z是操作类型x、y是操作的元素 cin z x y; if(z 1) // 操作1合并x和y所在的集合 { int fx find(x); // 找x的最终组长 int fy find(y); // 找y的最终组长 fa[fx] fy; // 把x的组长的父节点设为y的组长合并两组 } else // 操作2查询x和y是否同组 { // 若x和y的最终组长相同说明同组→输出Y否则输出N if(find(x) find(y)) cout Y endl; else cout N endl; } } return 0; }1.5.2亲戚题⽬来源 洛⾕题⽬链接P1551 亲戚难度系数 ★★若某个家族人员过于庞大要判断两个是否是亲戚确实还很不容易现在给出某个亲戚关系图求任意给出的两个人是否具有亲戚关系。题目描述规定x 和 y 是亲戚y 和 z 是亲戚那么 x 和 z 也是亲戚。如果 xy 是亲戚那么 x 的亲戚都是 y 的亲戚y 的亲戚也都是 x 的亲戚。输入格式第一行三个整数 n,m,pn,m,p≤5000分别表示有 n 个人m 个亲戚关系询问 p 对亲戚关系。以下 m 行每行两个数 Mi​Mj​1≤Mi​, Mj​≤n表示 Mi​ 和 Mj​ 具有亲戚关系。接下来 p 行每行两个数 Pi​,Pj​询问 Pi​ 和 Pj​ 是否具有亲戚关系。输出格式p 行每行一个Yes或No。表示第 i 个询问的答案为“具有”或“不具有”亲戚关系。输入输出样例输入 #1复制6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6输出 #1复制Yes Yes No【解法】具有亲戚关系的两个集合就合并在⼀个集合中。因此可以⽤并查集解决。【参考代码】#include iostream using namespace std; const int N 5010; // 数组最大容量5010因为n≤5000留10个余量 int n, m, p; // n人数m亲戚关系数p询问数 int fa[N]; // fa[i]第i个人的“亲戚组长”根节点 // find函数找第x个人的最终组长路径压缩提速 // 三元运算符fa[x]x就返回x否则递归找并压缩路径 int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } // un函数合并x和y的亲戚组un是union的缩写因为union是关键字不能用 void un(int x, int y) { int fx find(x); // 找x的最终组长 int fy find(y); // 找y的最终组长 fa[fy] fx; // 把y的组长的父节点设为x的组长合并两组 } // issame函数判断x和y是不是亲戚最终组长相同就是亲戚 bool issame(int x, int y) { return find(x) find(y); } int main() { cin n m p; // 初始化并查集每个人的组长都是自己初始无亲戚 for(int i 1; i n; i) fa[i] i; // 处理m组亲戚关系合并对应的人 while(m--) { int x, y; cin x y; un(x, y); // 合并x和y的亲戚组 } // 处理p个询问判断是不是亲戚输出Yes/No while(p--) { int x, y; cin x y; if(issame(x, y)) cout Yes\n; // 是亲戚输出Yes else cout No\n; // 不是输出No } return 0; }1.5.3Lake Counting题⽬来源 洛⾕题⽬链接P1596 [USACO10OCT] Lake Counting S难度系数 ★★由于最近的降雨水在农夫约翰的田地里积聚了。田地可以表示为一个 N×M 的矩形1≤N≤1001≤M≤100。每个方格中要么是水W要么是干地.。农夫约翰想要弄清楚他的田地里形成了多少个水塘。一个水塘是由连通的水方格组成的其中一个方格被认为与它的八个邻居相邻。给定农夫约翰田地的示意图确定他有多少个水塘。输入格式第 1 行两个用空格分隔的整数N 和 M。第 2 行到第 N1 行每行 M 个字符表示农夫约翰田地的一行。每个字符要么是W要么是.。字符之间没有空格。输出格式第 1 行农夫约翰田地中的水塘数量。显示翻译题意翻译输入输出样例输入 #1复制10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.输出 #1复制3说明/提示输出详情共有三个水塘一个在左上角一个在左下角还有一个沿着右侧。由 ChatGPT 4o 翻译【解法】遍历整个矩阵每次遇到⼀个⽔坑时就把这个⽔坑右、下左下以及右下的⽔坑合并在⼀起。最终判断⼀下⼀共有多少个集合。【参考代码】#include iostream using namespace std; const int N 110; // 网格最大100×100留10个余量 int n, m; // n行数m列数示例里n10m12 char a[N][N]; // 存储网格a[i][j]是第i行第j列的字符W/. int fa[N * N]; // 并查集数组fa[编号] 该位置的组长编号 i*m j // 方向数组只查4个关键方向右、下、右下、左下避免重复合并 // dx[k]是行偏移dy[k]是列偏移 int dx[] {0, 1, 1, 1}; // 行0同列、1下一行、1下一行、1下一行 int dy[] {1, 1, 0, -1}; // 列1右、1右下、0下、-1左下 // find函数找位置编号x的最终组长路径压缩 // 三元运算符如果x的组长是自己返回x否则递归找并压缩路径 int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } // un函数合并两个位置的集合x和y是一维编号 void un(int x, int y) { // 把x的组长的父节点设为y的组长 → 合并两个集合 fa[find(x)] find(y); } int main() { cin n m; // 读入行数n和列数m // 读入网格逐行逐列存字符W/. for(int i 0; i n; i) for(int j 0; j m; j) cin a[i][j]; // 初始化并查集每个位置的组长都是自己不管是W还是. for(int i 0; i n * m; i) fa[i] i; // 遍历每个网格位置 for(int i 0; i n; i) // 遍历第i行 { for(int j 0; j m; j) // 遍历第j列 { if(a[i][j] .) continue; // 是旱地跳过 // 检查4个关键方向的网格 for(int k 0; k 4; k) { // 计算目标位置的行x、列y int x i dx[k]; int y j dy[k]; // 边界判断y≥0列不越左界 xn行不越下界 目标位置是W if(x n y 0 a[x][y] W) { // 把当前位置i,j和目标位置x,y合并 // 一维编号i*mj当前、x*my目标 un(i * m j, x * m y); } } } } // 统计水坑数遍历所有位置数“是W且组长是自己”的数量 int ret 0; // ret存水坑数初始为0 for(int i 0; i n * m; i) { // 一维编号转二维坐标x行y列 int x i / m; // 行号 编号 ÷ 列数比如i12m12 → x1 int y i % m; // 列号 编号 % 列数比如i12m12 → y0 // 如果该位置是W且组长是自己 → 是一个独立水坑 if(a[x][y] W fa[i] i) ret; } cout ret endl; // 输出水坑数 return 0; }1.5.4程序⾃动分析题⽬来源 洛⾕题⽬链接P1955 [NOI2015] 程序⾃动分析难度系数 ★★★题目描述在实现程序自动分析的过程中常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本假设 x1​,x2​,x3​,⋯ 代表程序中出现的变量给定 n 个形如 xi​xj​ 或 xi​xj​ 的变量相等/不等的约束条件请判定是否可以分别为每一个变量赋予恰当的值使得上述所有约束条件同时被满足。例如一个问题中的约束条件为x1​x2​,x2​x3​,x3​x4​,x4​x1​这些约束条件显然是不可能同时被满足的因此这个问题应判定为不可被满足。现在给出一些约束满足问题请分别对它们进行判定。输入格式输入的第一行包含一个正整数 t表示需要判定的问题个数。注意这些问题之间是相互独立的。对于每个问题包含若干行第一行包含一个正整数 n表示该问题中需要被满足的约束条件个数。接下来 n 行每行包括三个整数 i,j,e描述一个相等/不等的约束条件相邻整数之间用单个空格隔开。若 e1则该约束条件为 xi​xj​。若e0则该约束条件为 xi​xj​。输出格式输出包括 t 行。输出文件的第 k 行输出一个字符串YES或者NO字母全部大写YES表示输入中的第 k 个问题判定为可以被满足NO表示不可被满足。输入输出样例输入 #1复制2 2 1 2 1 1 2 0 2 1 2 1 2 1 1输出 #1复制NO YES输入 #2复制2 3 1 2 1 2 3 1 3 1 1 4 1 2 1 2 3 1 3 4 1 1 4 0输出 #2复制YES NO说明/提示【样例解释1】在第一个问题中约束条件为x1​x2​,x1​x2​。这两个约束条件互相矛盾因此不可被同时满足。在第二个问题中约束条件为x1​x2​,x1​x2​。这两个约束条件是等价的可以被同时满足。【样例说明2】在第一个问题中约束条件有三个x1​x2​,x2​x3​,x3​x1​。只需赋值使得 x1​x2​x3​即可同时满足所有的约束条件。在第二个问题中约束条件有四个x1​x2​,x2​x3​,x3​x4​,x4​x1​。由前三个约束条件可以推出 x1​x2​x3​x4​然而最后一个约束条件却要求 x1​x4​因此不可被满足。【数据范围】所有测试数据的范围和特点如下表所示测试点编号n 的规模i,j 的规模约定11≤n≤101≤i,j≤1041≤t≤10e∈{0,1}231≤n≤100451≤n≤1056781≤n≤1051≤i,j≤109910【解法】先利⽤并查集维护所有相等的信息然后遍历所有的不相等信息判断⼀下是否合法。因为数据范围的问题需要先对所有的数离散化处理。【参考代码】#include iostream #include unordered_map // 哈希表用于离散化映射 #include algorithm // 排序离散化需要 using namespace std; const int N 1e5 10; // 约束条件最多10万条 int n; // 每个问题的约束数 // 存储每个约束条件x变量iy变量je1相等/0不等 struct node { int x, y, e; }a[N]; // 离散化相关变量 int pos; // 记录所有出现过的变量编号数量 int disc[N * 2]; // 存储所有出现过的变量编号去重前 unordered_mapint, int mp; // 映射表原编号→离散化后的小编号 // 并查集数组 int fa[N * 2]; // find函数找离散化后编号x的最终组长路径压缩 int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } // un函数合并两个离散化后的编号x和y void un(int x, int y) { fa[find(x)] find(fa[y]); } // issame函数判断两个离散化后的编号是否在同一集合 bool issame(int x, int y) { return find(x) find(y); } // 处理单个问题的函数返回true满足/false不满足 bool solve() { cin n; // 读入当前问题的约束数 // 清空离散化相关数据多组测试用例避免干扰 pos 0; mp.clear(); // 第一步读入所有约束收集所有出现过的变量编号 for(int i 1; i n; i) { cin a[i].x a[i].y a[i].e; // 把变量x、y存入disc数组后续离散化用 disc[pos] a[i].x; disc[pos] a[i].y; } // 第二步离散化大编号→小编号 // 1. 对disc数组排序方便去重 sort(disc 1, disc 1 pos); int cnt 0; // 离散化后的编号从1开始 for(int i 1; i pos; i) { int x disc[i]; if(mp.count(x)) continue; // 已经映射过跳过去重 cnt; // 新的小编号 mp[x] cnt; // 记录映射关系比如x1→1 } // 第三步初始化并查集离散化后的编号从1到cnt for(int i 1; i cnt; i) fa[i] i; // 第四步处理所有相等约束e1合并变量 for(int i 1; i n; i) { int x a[i].x, y a[i].y, e a[i].e; if(e 1) // 相等约束合并x和y的离散化编号 un(mp[x], mp[y]); } // 第五步检查所有不等约束e0判断是否矛盾 for(int i 1; i n; i) { int x a[i].x, y a[i].y, e a[i].e; if(e 0) // 不等约束 { // 如果x和y在同一集合本该不等却相等→ 矛盾返回false if(issame(mp[x], mp[y])) return false; } } // 所有约束都满足返回true return true; } int main() { int T; cin T; // 读入问题个数 while(T--) // 处理每个问题 { if(solve()) // 满足所有约束 cout YES endl; else // 不满足 cout NO endl; } return 0; }1.6扩展域并查集普通的并查集只能解决各元素之间仅存在⼀种相互关系⽐如《亲戚》题⽬中•a和b是亲戚关系b和c是亲戚关系这时就可以查找出a和c也存在亲戚关系。但如果存在各元素之间存在多种相互关系普通并查集就⽆法解决。⽐如下⾯的案例• a和b 是敌⼈关系b 和 c是敌⼈关系但是a 和c 其实不是敌⼈关系⽽是另⼀种朋友关系。此时就不仅仅是简单的敌⼈关系还是出现⼀种朋友关系。解决这类问题就需要对并查集进⾏扩展将每个元素拆分成多个域每个域代表⼀种状态或者关系。通过维护这些域之间的关系来处理复杂的约束条件。敌⼈朋友问题中我们会将x分成两个域朋友域x以及敌⼈域y•x和y是朋友正常处理把x和y合并成⼀个集合• x和 y是敌⼈那么x 和y 的敌⼈yn 就是朋友合并x 与yn y和 x的敌⼈xn就是朋友合并y 与 xn。这样就可以利⽤两个域将所有的关系维护起来。1.6.1团伙题⽬来源 洛⾕题⽬链接P1892 [BOI2003] 团伙难度系数 ★★★题目描述现在有 n 个人他们之间有两种关系朋友和敌人。我们知道一个人的朋友的朋友是朋友一个人的敌人的敌人是朋友现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。输入格式第一行输入一个整数 n 代表人数。第二行输入一个整数 m 表示接下来要列出 m 个关系。接下来 m 行每行一个字符 opt 和两个整数 p,q分别代表关系朋友或敌人有关系的两个人之中的第一个人和第二个人。其中 opt 有两种可能如果 opt 为F则表明 p 和 q 是朋友。如果 opt 为E则表明 p 和 q 是敌人。输出格式一行一个整数代表最多的团体数。输入输出样例输入 #1复制6 4 E 1 4 F 3 5 F 4 6 E 1 2输出 #1复制3说明/提示对于 100% 的数据2≤n≤10001≤m≤50001≤p,q≤n。【解法】扩展域并查集模板题•a和b如果是朋友那就直接合并在⼀起•a和b如果是敌⼈那就把a和bn以及an和b合并在⼀起。【参考代码】#include iostream using namespace std; const int N 1010; // 人数最多1000扩展域后是2000留10余量 int n, m; // n人数m关系数 int fa[N * 2]; // 扩展域并查集1~n是原域朋友n1~2n是敌域敌人 // find函数找x的最终组长路径压缩 int find(int x) { // 三元运算符x的组长是自己则返回x否则递归找并压缩路径 return fa[x] x ? x : fa[x] find(fa[x]); } // un函数合并x和y让y的组长指向x的组长保证朋友域为父节点 void un(int x, int y) { fa[find(y)] find(x); } int main() { cin n m; // 读入人数n和关系数m // 初始化扩展域并查集1~2n的每个位置组长都是自己 for(int i 1; i n * 2; i) fa[i] i; // 处理m个关系 while(m--) { char op; // 关系类型F朋友/E敌人 int x, y; // 有关系的两个人 cin op x y; if(op F) // 朋友关系合并x和y的原域 { un(x, y); } else // 敌人关系合并x和y的敌域、y和x的敌域 { un(x, y n); // x 加入 y的敌域 un(y, x n); // y 加入 x的敌域 } } // 统计团体数原域1~n中组长是自己的数量 int ret 0; for(int i 1; i n; i) { if(fa[i] i) ret; } cout ret endl; // 输出团体数 return 0; }1.6.2⻝物链题⽬来源 洛⾕题⽬链接P2024 [NOI2001] ⻝物链难度系数 ★★★题目描述动物王国中有三类动物 A,B,C这三类动物的食物链构成了有趣的环形。A 吃 BB 吃 CC 吃 A。现有 N 个动物以 1∼N 编号。每个动物都是 A,B,C 中的一种但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述第一种说法是1 X Y表示 X 和 Y 是同类。第二种说法是2 X Y表示 X 吃 Y。此人对 N 个动物用上述两种说法一句接一句地说出 K 句话这 K 句话有的是真的有的是假的。当一句话满足下列三条之一时这句话就是假话否则就是真话。当前的话与前面的某些真的话冲突就是假话当前的话中 X 或 Y 比 N 大就是假话当前的话表示 X 吃 X就是假话。你的任务是根据给定的 N 和 K 句话输出假话的总数。输入格式第一行两个整数N,K表示有 N 个动物K 句话。第二行开始每行一句话。格式见题目描述与样例。输出格式一行一个整数表示假话的总数。输入输出样例输入 #1复制100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5输出 #1复制3说明/提示对于全部数据1≤N≤5×1041≤K≤105。【解法】针对x扩展三个域同类域 x捕⻝域 x n被捕⻝域 x n n。如果 x 和 y 是同类•x 和 y 是同类•x n 与 y n 是同类•x n n 与 y n n 是同类如果 x 捕⻝ y• x n 与 y 同类• x 与 y n n 同类• x n n 与 y n 同类【参考代码】#include iostream using namespace std; const int N 5e4 10; // 动物最多5万三倍扩展后15万10 int n, k; // n动物数k话的数量 int fa[N * 3]; // 三倍扩展域并查集1~n(同类)、n1~2n(捕食)、2n1~3n(被捕食) // find函数找x的最终组长路径压缩提速 int find(int x) { return x fa[x] ? x : fa[x] find(fa[x]); } // un函数合并x和y的集合让x的组长指向y的组长 void un(int x, int y) { fa[find(x)] find(y); } int main() { cin n k; // 初始化扩展域并查集1~3n的每个位置组长都是自己 for(int i 1; i n * 3; i) fa[i] i; int ret 0; // 统计假话数量初始为0 // 处理k句话 while(k--) { int op, x, y; cin op x y; // 假话条件2X或Y超过n → 直接记假话 if(x n || y n) { ret; continue; // 跳过后续判断 } if(op 1) // 第1种说法X和Y是同类 { // 冲突判定X在Y的捕食域find(x)find(yn)或被捕食域find(x)find(y2n) if(find(x) find(y n) || find(x) find(y 2 * n)) { ret; // 假话计数1 } else { // 合并同类域、捕食域、被捕食域 un(x, y); // 同类域合并 un(x n, y n); // 捕食域合并 un(x 2 * n, y 2 * n); // 被捕食域合并 } } else // 第2种说法X吃Y { // 冲突判定X和Y是同类find(x)find(y)或X在Y的捕食域Y吃X冲突 if(find(x) find(y) || find(x) find(y n)) { ret; // 假话计数1 } else { // 合并规则X吃Y → 维护三种关系 un(x, y 2 * n); // X的同类域 ↔ Y的被捕食域 un(y, x n); // Y的同类域 ↔ X的捕食域 un(x 2 * n, y n); // X的被捕食域 ↔ Y的捕食域 } } } cout ret endl; // 输出假话总数 return 0; }1.7带权并查集1.带权并查集的概念带权并查集在普通并查集的基础上为每个结点增加了⼀个权值。这个权值可以表⽰当前结点与⽗结 点之间的关系、距离或其他信息注意由于我们有路径压缩操作所以最终这个权值表⽰的是当前 结点相对于根结点的信息。有了这样⼀个权值就可以推断出集合中各个元素之间的相互关系。2.带权并查集的实现我们以最简单的距离问题为例实现⼀个能够查询任意两点之间距离的并查集。 实现带权并查集的核⼼是在进⾏ Find和Union操作时不仅要维护集合的结构还要维护结点的权值。注意带权并查集的实现是多种多样的基本上换⼀道题实现的代码就要更改。因此⼀定要重点关 注实现过程的思考⽅式这才是通⽤的。初始化initconst int N 1e5 10, INF 0x3f3f3f3f; int n; int fa[N], d[N]; void init() { for(int i 1; i n; i) { fa[i] i; d[i] 0; // 根据题⽬要求来初始化 } }查询根节点操作findint find(int x) { if(fa[x] x) return x; int t find(fa[x]); // 这句代码⼀定要先执⾏先让⽗结点挂在根节点的后⾯ d[x] d[fa[x]]; // 注意可能会根据权值的意义有所改变 return fa[x] t; }合并操作union// x 所在集合与 y 所在集合合并x 与 y 之间的权值是 w void un(int x, int y, int w) { int fx find(x), fy find(y); if(fx ! fy) // 不在同⼀个集合中 { fa[fx] fy; d[fx] d[y] w - d[x]; // 注意可能会根据权值的意义有所改变 } }查询距离操作query// 查询 x 到 y 的距离 int query(int x, int y) { int fx find(x), fy find(y); if(fx ! fy) return INF; // 如果不在同⼀个集合中说明距离未知 return d[y] - d[x]; }1.7.1⻝物链题⽬来源 洛⾕题⽬链接P2024 [NOI2001] ⻝物链难度系数 ★★★题目描述动物王国中有三类动物 A,B,C这三类动物的食物链构成了有趣的环形。A 吃 BB 吃 CC 吃 A。现有 N 个动物以 1∼N 编号。每个动物都是 A,B,C 中的一种但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述第一种说法是1 X Y表示 X 和 Y 是同类。第二种说法是2 X Y表示 X 吃 Y。此人对 N 个动物用上述两种说法一句接一句地说出 K 句话这 K 句话有的是真的有的是假的。当一句话满足下列三条之一时这句话就是假话否则就是真话。当前的话与前面的某些真的话冲突就是假话当前的话中 X 或 Y 比 N 大就是假话当前的话表示 X 吃 X就是假话。你的任务是根据给定的 N 和 K 句话输出假话的总数。输入格式第一行两个整数N,K表示有 N 个动物K 句话。第二行开始每行一句话。格式见题目描述与样例。输出格式一行一个整数表示假话的总数。输入输出样例输入 #1复制100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5输出 #1复制3说明/提示对于全部数据1≤N≤5×1041≤K≤105。【解法】把真话⾥⾯的相互关系⽤带权并查集维护起来权值表⽰当前节点相对于根节点的距离。那么对 于集合中的任意两点x和y• 如果 (d[y] −d[x]) % 3 0 表⽰两者是同类关系• 如果 (d[y] −d[x]) % 3 1 表⽰两者是捕⻝关系• 如果 (d[y] −d[x]) % 3 2 表⽰两者是天敌关系。find 操作• 更新d数组按照最基础的距离更新的⽅式 d[x] d[x] d[fa[x]] union 操作•如果x和y是同类那么边权就是0•如果x吃y那么边权就是1【参考代码】#include iostream using namespace std; const int N 5e4 10; // 动物最多5万足够存储 int n, k; // n动物数k话的数量 int fa[N], d[N]; // fa[]父节点d[]当前节点到根节点的权值距离 // find函数找x的根节点同时更新d[x]路径压缩权值更新 int find(int x) { if(fa[x] x) return x; // x是根节点直接返回 int t find(fa[x]); // 先找父节点的根递归 d[x] d[fa[x]]; // 更新x到根的权值x→父节点 父节点→根 return fa[x] t; // 路径压缩x直接指向根 } // un函数合并x和y的集合w是x和y的期望权值0同类2x吃y void un(int x, int y, int w) { int fx find(x), fy find(y); // 找x和y的根 if(fx ! fy) // 不在同一集合需要合并 { fa[fx] fy; // 把x的根挂到y的根上 // 核心更新fx到fy的权值保证(d[y]-d[x])%3 w d[fx] d[y] w - d[x]; } } int main() { cin n k; // 初始化每个动物的父节点是自己权值为0到自己的距离为0 for(int i 1; i n; i) fa[i] i; int ret 0; // 统计假话数量 while(k--) { int op, x, y; cin op x y; // 先处理边界X/Y超出范围 → 假话 if(x n || y n) { ret; continue; } // 提前找根后续判断冲突需要 int fx find(x), fy find(y); if(op 1) // 说法1X和Y是同类期望(d[y]-d[x])%30 { // 冲突条件同集合但权值差模3≠0 if(fx fy ((d[y] - d[x]) % 3 3) % 3 ! 0) { ret; } else { un(x, y, 0); // 合并期望权值0同类 } } else // 说法2X吃Y期望(d[y]-d[x])%32 → 对应x吃y { // 特殊情况XYX吃X→ 假话 if(x y) { ret; continue; } // 冲突条件同集合但权值差模3≠1注意代码里写的是≠1等价于≠2看推导 if(fx fy ((d[y] - d[x]) % 3 3) % 3 ! 1) { ret; } else { un(x, y, 2); // 合并期望权值2X吃Y } } } cout ret endl; return 0; }1.7.2银河英雄传说题⽬来源 洛⾕题⽬链接P1196 [NOI2002] 银河英雄传说难度系数 ★★★题目背景公元 5801 年地球居民迁至金牛座 α 第二行星在那里发表银河联邦创立宣言同年改元为宇宙历元年并开始向银河系深处拓展。宇宙历 799 年银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。题目描述杨威利擅长排兵布阵巧妙运用各种战术屡次以少胜多难免恣生骄气。在这次决战中他将巴米利恩星域战场划分成 30000 列每列依次编号为 1,2,…,30000。之后他把自己的战舰也依次编号为 1,2,…,30000让第 i 号战舰处于第 i 列形成“一字长蛇阵”诱敌深入。这是初始阵形。当进犯之敌到达时杨威利会多次发布合并指令将大部分战舰集中在某几列上实施密集攻击。合并指令为M i j含义为第 i 号战舰所在的整个战舰队列作为一个整体头在前尾在后接至第 j 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。然而老谋深算的莱因哈特早已在战略上取得了主动。在交战中他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。在杨威利发布指令调动舰队的同时莱因哈特为了及时了解当前杨威利的战舰分布情况也会发出一些询问指令C i j。该指令意思是询问电脑杨威利的第 i 号战舰与第 j 号战舰当前是否在同一列中如果在同一列中那么它们之间布置有多少战舰。作为一个资深的高级程序设计员你被要求编写程序分析杨威利的指令以及回答莱因哈特的询问。最终的决战已经展开银河的历史又翻过了一页……输入格式第一行有一个整数 T1≤T≤5×105表示总共有 T 条指令。以下有 T 行每行有一条指令。指令有两种格式M i ji 和 j 是两个整数1≤i,j≤30000表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令并且保证第 i 号战舰与第 j 号战舰不在同一列。C i ji 和 j 是两个整数1≤i,j≤30000表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。每条指令中都保证 ij。输出格式依次对输入的每一条指令进行分析和处理如果是杨威利发布的舰队调动指令则表示舰队排列发生了变化你的程序要注意到这一点但是不要输出任何信息。如果是莱因哈特发布的询问指令你的程序要输出一行仅包含一个整数表示在同一列上第 i 号战舰与第 j 号战舰之间布置的战舰数目。如果第 i 号战舰与第 j 号战舰当前不在同一列上则输出 −1。输入输出样例输入 #1复制4 M 2 3 C 1 2 M 2 4 C 4 2输出 #1复制-1 1说明/提示样例解释战舰位置图表格中阿拉伯数字表示战舰编号。【解法】这道题中有明显的边权关系因此可以⽤带权并查集解决。【参考代码】#include iostream #include cstdlib // 用于abs函数绝对值 using namespace std; const int N 3e4 10; // 战舰最多3万留10余量 int n 3e4; // 固定战舰总数30000 int fa[N], d[N], cnt[N]; // fa父节点d到父节点的距离cnt集合大小列战舰数 // find函数找x的根节点同时更新d[x]路径压缩权值更新 int find(int x) { if(fa[x] x) return x; // x是根节点直接返回 int t find(fa[x]); // 递归找父节点的根 d[x] d[fa[x]]; // 更新x到根的距离x→父 父→根 return fa[x] t; // 路径压缩x直接指向根 } // un函数合并x所在列到y所在列的尾部 void un(int x, int y) { int fx find(x), fy find(y); // 找x和y的根 if(fx ! fy) // 不在同一列执行合并 { fa[fx] fy; // 把x的根挂到y的根上 d[fx] cnt[fy]; // fx到fy的距离 y列的总战舰数 cnt[fy] cnt[fx]; // 合并后y列总数 原y列数 原x列数 } } // query函数查询x和y之间的战舰数 int query(int x, int y) { int fx find(x), fy find(y); // 找x和y的根 if(fx ! fy) return -1; // 根不同→不在同一列 // 根相同→距离差的绝对值减1中间的战舰数 return abs(d[x] - d[y]) - 1; } int main() { // 初始化每个战舰的父节点是自己距离为0列数为1 for(int i 1; i n; i) { fa[i] i; // 初始父节点是自己 d[i] 0; // 初始到自己的距离为0 cnt[i] 1; // 初始每列只有1艘战舰 } int T; cin T; // 读入指令总数 while(T--) { char op; int x, y; cin op x y; // 读入指令类型和战舰编号 if(op M) // 合并指令x列接在y列尾部 { un(x, y); } else // 查询指令C x y { cout query(x, y) endl; } } return 0; }