NOIP2026复赛并查集与最小生成树综合训练题

NOIP2026复赛并查集与最小生成树综合训练题第一题（3分）题目：基础并查集应用——社团查找某学校社团联合会需要对全校社团进行管理。已知有N个社团（编号为1到N），社团之间存在一定的关联关系，关系用边表示，边权表示社团间的关联度。现需要用并查集算法将关联度小于等于K的社团合并为同一个社团，并统计最终有多少个社团。输入：第一行输入两个整数N和M，分别表示社团数量和关系数量。接下来M行，每行输入三个整数u,v,w，表示社团u和社团v之间存在关联度w的关系。最后一行输入一个整数K。输出：一个整数，表示合并后的社团数量。示例：输入：561232323454511542432输出：2解析：-关联度小于等于2的关系有：1-2（3）、2-3（2）、2-4（3）。-合并后社团1、2、3、4属于同一个社团，社团5独立。-最终社团数量为2。第二题（4分）题目：最小生成树与并查集——网络连接问题某城市需要建设网络，连接N个区域。已知每两个区域之间建设连接的成本不同，需要选择一部分连接，使得所有区域都连通，且总成本最小。同时，部分连接可能因技术限制不能使用。请使用Kruskal算法结合并查集求解最小生成树问题，并统计最终的总成本。输入：第一行输入两个整数N和M，分别表示区域数量和连接数量。接下来M行，每行输入四个整数u,v,w,flag，表示区域u和区域v之间建设连接的成本为w，flag=1表示该连接可用，flag=0表示不可用。最后一行输入一个整数K，表示必须使用的连接数量（保证所有区域最终连通）。输出：一个整数，表示最终的最小总成本。示例：输入：45123123213451146024712输出：10解析：-可用的连接及成本：1-2（3）、2-3（2）、3-4（5）、2-4（7）。-必须使用的连接：2-4（7）。-最小生成树选择：1-2（3）、2-3（2）、2-4（7），总成本为12。-但需注意K=2，实际需选择2条边：1-2（3）、2-3（2），总成本为5。第三题（5分）题目：并查集与最小生成树——社团活动组织某社区有N个活动中心，需要连接部分中心，使得所有中心都可通过步行道到达。步行道有不同长度，且部分道路因限制无法使用。同时，社区需要组织至少K个活动，每个活动需选择一个中心作为起点。请用Kruskal算法结合并查集求解最小生成树，并统计所有活动中心的连通性是否满足条件。输入：第一行输入两个整数N和M，表示活动中心数量和道路数量。接下来M行，每行输入四个整数u,v,w,flag，表示中心u和中心v之间的道路长度为w，flag=1表示道路可用，flag=0表示不可用。最后一行输入一个整数K，表示必须组织活动的中心数量。输出：一个字符串，"YES"表示所有活动中心连通，"NO"表示不连通。示例：输入：6712312321345145111640256036313输出：YES解析：-可用的道路及长度：1-2（3）、2-3（2）、3-4（5）、4-5（1）、3-6（3）。-必须组织活动的中心数量K=3，需至少3个连通分量。-最小生成树选择：1-2（3）、2-3（2）、3-6（3），总长度8，但需检查连通性。-实际连通中心数量为4（1,2,3,6），满足K=3，输出"YES"。第四题（6分）题目：并查集与最小生成树——城市交通网络优化某城市有N个路口，需要建设道路连接所有路口，部分道路有成本限制。现需用最小生成树算法优化道路建设，同时满足以下条件：1.所有路口必须连通。2.道路总成本不超过预算C。3.若道路成本超过预算，需用并查集判断是否可以替代其他道路。输入：第一行输入三个整数N,M,C，分别表示路口数量、道路数量和预算。接下来M行，每行输入四个整数u,v,w,flag，表示路口u和v之间的道路成本为w，flag=1表示道路可用，flag=0表示不可用。最后一行输入一个整数K，表示必须使用的道路数量。输出：一个整数，表示满足条件的道路总成本，若不满足则输出-1。示例：输入：56124123313451452115602470102输出：14解析：-可用的道路及成本：1-2（4）、2-3（3）、3-4（5）、4-5（2）。-必须使用的道路数量K=2，优先选择成本较低的：1-2（4）、4-5（2），总成本6。-预算C=10，剩余预算4，可扩展其他道路：2-3（3），总成本9。-最终选择：1-2（4）、4-5（2）、2-3（3），总成本14≤10，输出14。第五题（7分）题目：并查集与最小生成树——校园网络规划某大学校园有N个建筑，需要建设网络连接所有建筑，部分连接因技术限制无法使用。同时，学校需要确保所有建筑在紧急情况下可通过至少两条路径连通（即最小生成树需要至少两个连通分量）。请用Kruskal算法结合并查集求解，并统计最终的网络成本。输入：第一行输入两个整数N和M，表示建筑数量和连接数量。接下来M行，每行输入四个整数u,v,w,flag，表示建筑u和v之间的连接成本为w，flag=1表示连接可用，flag=0表示不可用。最后一行输入一个整数K，表示必须使用的连接数量。输出：一个整数，表示最终的网络成本。若无法满足条件则输出-1。示例：输入：6712312321345145111640256036312输出：14解析：-可用的连接及成本：1-2（3）、2-3（2）、3-4（5）、4-5（1）、3-6（3）。-必须使用的连接数量K=2，优先选择成本较低的：1-2（3）、4-5（1），总成本4。-需要至少两个连通分量，可选择：1-2（3）、3-6（3），形成两个连通分量。-最终网络成本为6，满足条件，输出14。答案与解析第一题答案：2解析：-关联度小于等于2的关系有：1-2（3）、2-3（2）、2-4（3）。-合并后社团1、2、3、4属于同一个社团，社团5独立。-最终社团数量为2。第二题答案：10解析：-可用的连接及成本：1-2（3）、2-3（2）、3-4（5）、2-4（7）。-必须使用的连接：2-4（7）。-最小生成树选择：1-2（3）、2-3（2）、2-4（7），总成本12。-但需注意K=2，实际需选择2条边：1-2（3）、2-3（2），总成本5。第三题答案：YES解析：-可用的道路及长度：1-2（3）、2-3（2）、3-4（5）、4-5（1）、3-6（3）。-必须组织活动的中心数量K=3，需至少3个连通分量。-最小生成树选择：1-2（3）、2-3（2）、3-6（3），总长度8，但需检查连通性。-实际连通中心数量为4（1,2,3,6），满足K=3，输出"YES"。第四题答案：14解析：-可用的道路及成本：1-2（4）、2-3（3）、3-4（5）、4-5（2）。-必须使用的道路数量K=2，优先选择成本较低的：1-2（4）、4-5（2），总成本6。-预算C=10，剩余预算4，可扩展其他道路：2-3（3），总成本9。-最终选择：1-2（4）、4-5（2）、2-3（3），总成本14≤10，输出14。第五题答案：14解析：-可用的连接及成本：1-2（3）、2-3（2