蓝桥杯第793题——排水系统

news/2024/6/20 20:58:33/文章来源:https://blog.csdn.net/Ares_moran/article/details/137277290

题目描述

对于一个城市来说,排水系统是极其重要的一个部分。

有一天,小 C 拿到了某座城市排水系统的设计图。排水系统由 n 个排水结点(它们从 1∼n 编号)和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水(简称为该结点的汇集管道),也有若干个管道向其他的排水结点排出污水(简称为该结点的排出管道)。

排水系统的结点中有 m 个污水接收口,它们的编号分别为 1,2,…,m,污水只能从这些接收口流入排水系统,并且这些结点没有汇集管道。排水系统中还有若干个最终排水口,它们将污水运送到污水处理厂,没有排出管道的结点便可视为一个最终排水口。

现在各个污水接收口分别都接收了 1 吨污水,污水进入每个结点后,会均等地从当前结点的每一个排出管道流向其他排水结点,而最终排水口将把污水排出系统。

现在小 C 想知道,在该城市的排水系统中,每个最终排水口会排出多少污水。该城市的排水系统设计科学,管道不会形成回路,即不会发生污水形成环流的情况。

输入描述

第一行两个用单个空格分隔的整数 n,m。分别表示排水结点数与接收口数量。

接下来 n 行,第 i 行用于描述结点 i 的所有排出管道。其中每行第一个整数 di​ 表示其排出管道的数量,接下来 di​个用单个空格分隔的整数 a1​,a2​,…,adi​​ 依次表示管道的目标排水结点。 保证不会出现两条起始结点与目标结点均相同的管道。

其中,1 ≤ n ≤ 10^5,1 ≤ m ≤ 10,0 ≤ di ​≤ 5。

数据保证,污水在从一个接收口流向一个最终排水口的过程中,不会经过超过 1010 个中间排水结点(即接收口和最终排水口不算在内)。

输出描述

输出若干行,按照编号从小到大的顺序,给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出,即每行输出两个用单个空格分隔的整数 p,q,表示排出的污水体积为 \frac{p}{q}​ 。要求 p 与 q 互素,q=1 时也需要输出 q。

输入输出样例

示例 1

输入

5 1
3 2 3 5
2 4 5
2 5 4
0
0

输出

1 3
2 3

 解题思路

本题是有向无环图的拓扑排序,而拓扑排序其实就是在图上的搜索,本质上就是dfs和bfs。

这题是典型的有起点有终点的有向图,我们自然而然的想到使用bfs进行遍历,一般像这样的题我们有以下需要关注的点:

  1. 使用邻接表存储点很多的稀疏图;使用ru和chu两个长度为n的数组记录每个点的入度和出度;使用链式队列完成bfs等。
  2. 通常我们可以开辟dp数组记录节点状态,但是本题比较特殊,对于每个点的状态使用p和q组合的一个分数来表示,这样我们就可以利用p和q数组代替dp数组记录节点状态了。

这道题需要我们对分数除法、分数加法、分数约分的过程进行模拟,其内容笔者使用了一个addWater方法进行操作,调用了最大公约数gcd和最小公倍数lcm算法,属于算法有关基础数学知识的内容。

这里需要注意的是,由于分数可能很大,所以我们不仅需要使用long类型进行存储计算,还要对求最小公倍数的时候先除以最大公因数再乘第二个数,否则有可能溢出。

代码题解

具体的代码并没有难以理解的地方,以下是具体的代码:

import java.io.*;
import java.util.*;public class Main {static int n, m;static ArrayList<ArrayList<Integer>> edges;static int[] ru, chu;static long[] p, q;static Queue<Integer> qu;public static void main(String[] args) throws IOException {BufferedReader in = new BufferedReader(new InputStreamReader(System.in));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));String[] temp = in.readLine().split(" ");n = Integer.parseInt(temp[0]);m = Integer.parseInt(temp[1]);init();for (int i = 1; i <= n; i++) {temp = in.readLine().split(" ");int t = Integer.parseInt(temp[0]);chu[i] = t;for (int j = 1; j <= t; j++) {int next = Integer.parseInt(temp[j]);edges.get(i).add(next);ru[next]++;}}for (int i = 1; i <= m; i++) {qu.add(i);p[i] = 1;q[i] = 1;}while (!qu.isEmpty()) {int t = qu.poll();for (int e : edges.get(t)) {addWater(t, e, chu[t]);ru[e]--;if (ru[e] == 0 && chu[e] > 0) {qu.add(e);}}p[t] = 0;q[t] = 0;}for (int i = 1; i <= n; i++) {if (p[i] != 0) {out.print(p[i]);out.print(" ");out.print(q[i]);out.print("\n");}}out.flush();}public static void addWater(int sourse, int target, int num) {long p1 = p[sourse];long q1 = q[sourse];long t = gcd(p1, num);p1 /= t;q1 *= num / t;long p2 = p[target];long q2 = q[target];if (p2 == 0) {p[target] = p1;q[target] = q1;} else {long x = lcm(q1,  q2);long t1 = x / q1 * p1 + x / q2 * p2;long t2 = x;long tt = gcd(t1, t2);p[target] = t1 / tt;q[target] = t2 / tt;}}public static long gcd(long a, long b) {return a % b == 0 ? b : gcd(b, a % b);}public static long lcm(long a, long b) {return a / gcd(a, b) * b;}public static void init() {edges = new ArrayList<>();for (int i = 0; i <= n; i++) {edges.add(new ArrayList<>());}p = new long[n + 1];q = new long[n + 1];ru = new int[n + 1];chu = new int[n + 1];qu = new LinkedList<>();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1034780.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vulnhub之devguru靶场提权过程(vulnhub打靶日记)

一、环境搭建 VM版本&#xff1a;17.5.1 build-23298084 攻击机&#xff1a;Kali2024&#xff08;下载地址&#xff1a;https://www.kali.org/&#xff09; 靶机&#xff1a;vulnhub靶场Devguru&#xff08;下载地址&#xff1a;https://www.vulnhub.com/entry/devguru-1,62…

开源推荐榜【Pear Admin Flask 用python来创建后台管理系统】

最新技术高效快速开发&#xff0c;前后端分离模式&#xff0c;开箱即用。 核心模块包括&#xff1a;用户、角色、职位、组织机构、菜单、字典、日志、多应用管理、文件管理、定时任务等功能。 代码量少、学习简单、功能强大、轻量级、易扩展&#xff0c;轻松开发从现在开始&…

使用deepspeed小记

1. 减少显存占用的历程忠告 医学图像经常很大&#xff0c;所以训练模型有时候会有难度&#xff0c;但是现在找到了很多减少显存的方法。 不知道为什么&#xff0c;使用transformers的trainer库确确实实会减少显存的占用&#xff0c;即使没有使用deepspeed&#xff0c;占用的显…

重读 Java 设计模式: 深入探讨原型模式,灵活复制对象

引言 在软件开发中&#xff0c;经常会遇到需要创建对象的情况。有时候&#xff0c;我们希望创建一个新的对象&#xff0c;但又不想通过传统的构造方法来创建&#xff0c;而是希望通过复制一个现有对象的方式来创建新的对象。这时&#xff0c;原型模式就能派上用场了。原型模式…

环信IM集成教程——Web端UIKit快速集成与消息发送

写在前面&#xff1a; 千呼万唤始出来&#xff0c;环信Web端终于出UIKit了&#xff01;&#x1f389;&#x1f389;&#x1f389; 文档地址&#xff1a;https://doc.easemob.com/uikit/chatuikit/web/chatuikit_overview.html 环信单群聊 UIKit 是基于环信即时通讯云 IM SDK 开…

【六 (2)机器学习-机器学习建模步骤/kaggle房价回归实战】

一、确定问题和目标&#xff1a; 1、业务需求分析&#xff1a; 与业务团队或相关利益方进行深入沟通&#xff0c;了解他们的需求和期望。 分析业务流程&#xff0c;找出可能的瓶颈、机会或挑战。 思考机器学习如何帮助解决这些问题或实现业务目标。 2、问题定义&#xff1a;…

Java | Leetcode Java题解之第8题字符串转换整数atoi

题目&#xff1a; 题解&#xff1a; class Solution {public int myAtoi(String str) {Automaton automaton new Automaton();int length str.length();for (int i 0; i < length; i) {automaton.get(str.charAt(i));}return (int) (automaton.sign * automaton.ans);} …

基础布局之LinearLayout线性布局

目录 一、基础属性二、重点属性2.1 weight(权重)属性&#xff1a;2.2 gravity 一、基础属性 LinearLayout默认方向是水平排放 属性作用android:id控件的ID&#xff0c;可以通过这个ID号来找到对应的控件android:layout_width控件的宽度android:layout_height控件的高度androi…

[C语言实现]数据结构二叉树之《我种下的树会为我遮阳挡雨》

&#x1f970;作者: FlashRider &#x1f30f;专栏: 初阶数据结构 &#x1f356;知识概要&#xff1a;详解二叉树的概念、二叉树的遍历、以及代码实现。 目录 树的基本概念 树的存储结构与二叉树的实现 树的存储 什么是二叉树 二叉链存储二叉树 二叉树的代码实现 树的基本…

gpt 3d三角形 重心坐标填充 沿x轴炫赵师傅

go import pygame from pygame.locals import * import sys import math# 初始化Pygame pygame.init()# 设置窗口大小 width, height 800, 600 screen pygame.display.set_mode((width, height)) pygame.display.set_caption(3D Triangle Fill with Barycentric Coordinates)…

海豚调度任务类型Apache SeaTunnel部署指南

Apache DolphinScheduler已支持Apache SeaTunnel任务类型&#xff0c;本文介绍了SeaTunnel任务类型如何创建&#xff0c;任务参数&#xff0c;以及任务样例。 一、Apache SeaTunnel SeaTunnel 任务类型&#xff0c;用于创建并执行 SeaTunnel 类型任务。worker 执行该任务的时…

Kaggle:收入分类

先看一下数据的统计信息 import pandas as pd # 加载数据&#xff08;保留原路径&#xff0c;但在实际应用中建议使用相对路径或环境变量&#xff09; data pd.read_csv(r"C:\Users\11794\Desktop\收入分类\training.csv", encodingutf-8, encoding_errorsrepl…

基于单片机智能输液器监控系统的设计

**单片机设计介绍&#xff0c;基于单片机智能输液器监控系统的设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机智能输液器监控系统的设计旨在实现对输液过程的实时监测和控制&#xff0c;以提高输液的安全性和疗效…

C++:函数重载,引用

文章目录 1. 函数重载1.1 函数重载概念1.2 C支持函数重载的原理--名字修饰1.3 缺省参数与重载 2. 引用2.1引用概念2.2 引用特性2.3 常引用2.4 使用场景2.5 引用和指针的区别 1. 函数重载 1.1 函数重载概念 C允许在同一作用域中声明几个功能类似的同名函数&#xff0c;这些同名…

氮气柜常用的制作材质有哪些?

氮气柜主要用于存储对湿度敏感或需要在低氧环境中保存的精密部件、电子元器件、化学品、文物等&#xff0c;需要确保柜体的密闭性和内部环境的稳定&#xff0c;以防止氧化、受潮或变质。 常见的材质有冷轧钢板&#xff0c;冷轧钢板通过冷轧工艺使钢材组织更紧密&#xff0c;从而…

OpenHarmony实战:Vmware虚拟机和Ubuntu安装

避坑指南 1. 虚拟机命名、用户名称、路径不能有汉字 名称或者路径有汉字&#xff0c;导致输入失败或者安装失败 2. 虚拟机处理器内核总数&#xff08;处理器数量 X 每个处理器的内核数量&#xff09;不得超过电脑逻辑处理器总个数 太少时&#xff0c;下载代码和编译非常缓慢…

go连接数据库(原生)

根据官网文档 Go Wiki: SQL Database Drivers - The Go Programming Language 可以看到go可以连接的关系型数据库 ​ 常用的关系型数据库基本上都支持&#xff0c;下面以mysql为例 下载mysql驱动 打开上面的mysql链接 GitHub - go-sql-driver/mysql: Go MySQL Driver i…

图神经网络实战(7)——图卷积网络(Graph Convolutional Network, GCN)详解与实现

图神经网络实战&#xff08;7&#xff09;——图卷积网络详解与实现 0. 前言1. 图卷积层2. 比较 GCN 和 GNN2.1 数据集分析2.2 实现 GCN 架构 小结系列链接 0. 前言 图卷积网络 (Graph Convolutional Network, GCN) 架构由 Kipf 和 Welling 于 2017 年提出&#xff0c;其理念是…

JavaScript实现全选、反选功能(Vue全选、反选,js原生全选、反选)

简介&#xff1a; 在JavaScript中&#xff0c;实现全选和反选通常是通过操作DOM元素和事件监听来实现&#xff1b; 全选功能&#xff1a;当用户点击一个“全选”复选框时&#xff0c;页面中所有具有相同类名的复选框都将被选中&#xff1b; 反选功能&#xff1a;用户点击一个…

正则表达式(1)

文章目录 专栏导读1、match2、匹配目标3、通用匹配4、常用匹配规则表格 专栏导读 ✍ 作者简介&#xff1a;i阿极&#xff0c;CSDN 数据分析领域优质创作者&#xff0c;专注于分享python数据分析领域知识。 ✍ 本文录入于《python网络爬虫实战教学》&#xff0c;本专栏针对大学生…