2024.8.17
130124202408171002
DATE #:20240817
ITEM #:DOC
WEEK #:SATURDAY
DAIL #:捌月拾肆
TAGS< BGM = "快哉风 -- 黄金玉米王" > < theme = oi-language > < theme = oi-graph theory > < [空] > < [空] >取次花丛懒回顾,半缘修道半缘君 -- 元稹《离思五首·其四》
[P4208 [JSOI2008] 最小生成树计数]([P4208 JSOI2008] 最小生成树计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
[JSOI2008] 最小生成树计数
题目描述
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树,而希望知道这个图中有多少个不同的最小生成树。(如果两棵最小生成树中至少有一条边不同,则这两个最小生成树就是不同的)。由于不同的最小生成树可能很多,所以你只需要输出方案数对 31011 31011 31011 的模就可以了。
输入格式
第一行包含两个数, n n n 和 m m m,其中 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100, 1 ≤ m ≤ 1000 1 \le m \le 1000 1≤m≤1000,表示该无向图的节点数和边数。每个节点用 1 ∼ n 1 \sim n 1∼n 的整数编号。
接下来的 m m m 行,每行包含两个整数: a , b , c a,b,c a,b,c,表示节点 a , b a,b a,b 之间的边的权值为 c c c,其中 1 ≤ c ≤ 1 0 9 1 \le c \le 10^9 1≤c≤109。
数据保证不会出现自回边和重边。注意:具有相同权值的边不会超过 10 10 10 条。
输出格式
输出不同的最小生成树有多少个。你只需要输出数量对 31011 31011 31011 的模就可以了。
样例 #1
样例输入 #1
4 6 1 2 1 1 3 1 1 4 1 2 3 2 2 4 1 3 4 1样例输出 #1
8提示
数据范围及约定
对于全部数据, 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100, 1 ≤ m ≤ 1000 1 \le m \le 1000 1≤m≤1000, 1 ≤ c i ≤ 1 0 9 1\leq c_i\leq 10^9 1≤ci≤109。
先引入一个引理:
对于一个图的最小生成树,每个边权的边出现的次数是一样的
证明:模拟kruskal的过程,我们在给边排序时,交换同权的边并没有什么影响
那么我们先求解出最小生成树,并依次计算权值
考虑,当我们要加入权值为 i i i的若干条边时,
前面加入的边已经使其变成了几个联通块,只要考虑用权值为 i i i的边跑一次生成树数量即可,
之后对每个边权都依次操作
CODE //2024.8.17//by white_ice//[JSOI2008] 最小生成树计数 |P4208#include相关文章:
2024.8.17
130124202408171002 DATE #:20240817 ITEM #:DOC WEEK #:SATURDAY DAIL #:捌月拾肆 TAGS < BGM "快哉风 -- 黄金玉米王" > < theme oi-language > < theme oi-graph theory > < [空] > < [空] >取次花丛懒回顾,半缘修道…...
十分钟搭建一个RTMP服务器
使用SRS搭建RTMP服务器 如果您需要搭建一个RTMP服务器,您可以使用SRS(Simple-RTMP-Server)来完成此任务。SRS是一个开源的RTMP服务器下面是一个简单的步骤指南: 获取srs srs官⽹:https://github.com/ossrs/srs 码云…...
Spring Boot解决循环注入问题
Spring Boot解决循环依赖注入问题 代码问题回显启动错误日志解决方案:使用事件驱动或通过 ApplicationContext 手动获取 Bean1. 事件驱动设计2. 使用 ApplicationContext 手动获取 Bean3. 拆分逻辑 总结 代码问题回显 现有代码1 在InterestService中依赖MemberInte…...
《数据挖掘》期末考核重点
1.数据预处理的目的与形式 数据预处理的目的是提供干净,简洁,准确的数据,以达到简化模型和提高算法泛化能力的目的,使挖掘过程更有效,更容易,提高挖掘效率和准确性。 2.数据预处理的形式 数据清理&#…...
Golang | Leetcode Golang题解之第334题递增的三元子序列
题目: 题解: func increasingTriplet(nums []int) bool {n : len(nums)if n < 3 {return false}first, second : nums[0], math.MaxInt32for i : 1; i < n; i {num : nums[i]if num > second {return true} else if num > first {second n…...
HarmonyOs编写一个案例实现一个照片选择(阶段进阶 四种需求 逐一完善)
需求1. .实现照片选择 并将选择好的照片展示出来 import { GoodItem } from ../06/modules;Entry Component struct PhotoPage {State message: string 实现一个相册;State List: GoodItem[] [{goods_name: dsfjlsjkfsf,goods_price: 100,goods_img: https://img1.baidu.com…...
洗衣机洗衣服一些知识
01智能:按衣物多少自动调节合适水位的标准洗涤程序 (需要30分钟时间) 02:大物:较大,较厚的衣服洗涤 03:轻柔:毛织品或内衣洗涤 04:快速:少量清污衣服洗涤 (13分钟) 05:浸泡:先浸泡一段时间再洗涤 06:单洗:只洗衣不脱水 07:单脱:只脱水不洗衣 08:洁桶:清洁洗衣桶 准备工作: (1)…...
探索文件系统:高效、可靠的文件管理与访问机制
文件系统的功能规划 内存就像是一个书包,容量有限,只能带着一部分东西。而图书馆则是一个专门存储和管理文件的地方,拥有更大的容量,并且可以永久保存文件。为了能够快速找到需要的文件,我们需要有一个书单来记录每本…...
启程与远征Ⅸ--优化生成式人工智能以满足业务需求的框架
生成类似人类的文本和语音曾经只存在于科幻小说中。但 GPT-3 和 PaLM 等大型语言模型 (LLM) 的快速发展让这一愿景更接近现实,解锁了从聊天机器人到内容创作等一系列有前景的商业应用。 然而,通用基础模型往往无法满足行业用例的需求。企业对其生成式 A…...
canal数据同步工具介绍与应用
canal服务 canal介绍canal版本与环境canal 服务集canal应用场景: canal常见问题xml配置问题连接认证问题jar版本问题连接问题 canal介绍 1、Canal是阿里巴巴开源的MySQL增量数据订阅和消费工具,通过模拟MySQL的slave与master交互,捕…...
ubuntu18.04 设置静态地址
修改配置文件 sudo vim /etc/netplan/01-network-manager-all.yaml 代码如下: network: version: 2 renderer: NetworkManager ethernets: ens33: # 配置的网卡名称,可以使用ifconfig -a查看本机的网卡 dhcp4: no # 关闭动态IP设置 …...
jira敏捷开发管理工具视频教程Confluence工作流协同开发(2024)
正文: 随着Jira敏捷开发方法论的普及,Jira已经成为全球软件开发团队管理项目、任务和问题的首选工具。为了帮助团队更好地掌握Jira的核心功能,精心准备了一套全面开发技术及案例视频教程——《Jira敏捷开发管理工具视频教程Confluenc…...
【网络】TCP回显服务器和客户端的构造,以及相关bug解决方法
文章目录 ServerSocket构造方法方法 Socket构造方法方法 回显服务器(Echo Server)1. 构造方法2. 建立连接processConnection 方法的创建1. 读取请求并解析2. 根据请求计算响应3. 把响应写回给客户端 3. 完整代码 客户端(Echo Clientÿ…...
Python知识点:如何使用Boto3进行AWS服务管理
使用 boto3 来管理 AWS 服务是一个非常强大的方式,因为 boto3 是 AWS 提供的官方 Python SDK。下面是使用 boto3 管理 AWS 服务的基本步骤,包括设置、操作和常见的 AWS 服务示例。 1. 安装 boto3 首先,确保你已经安装了 boto3。可以使用 pi…...
Java - 正则表达式
Java 提供了 java.util.regex 包,它包含了 Pattern 和 Matcher 类,用于处理正则表达式的匹配操作。 正则表达式的模式 正则表达式的模式可以包括以下内容: 字面值字符:例如字母、数字、空格等,可以直接匹配它们自身。…...
Vue一款流行的JavaScript前端框架
1.Vue简介 Vue是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建,并提供了一套声明式的、组件化的编程模型,帮助你高效地开发用户界面。无论是简单还是复杂的界面,Vue 都可以胜任。 Vue所关注的核心是MVC…...
GPT-SoVITS
文章目录 model archS1 ModelS2 model model arch S1 model: AR model–ssl tokensS2 model: VITS,ssl 已经是mel 长度线性相关,MRTE(ssl_codes_embs, text, global_mel_emb)模块,将文本加强相关,学到一个参考结果 S1 Model cla…...
linux高级编程——文件IO(常用函数大全)
1.相关介绍及常用函数 Linux高级编程中的目录IO操作是文件系统编程的一个重要组成部分,主要涉及到目录的打开、读取、遍历和关闭等操作。以下是一些基本的目录IO操作和相关的系统调用函数 1.1 opendir函数 打开目录:使用opendir函数打开一个目录&#…...
matplotlib画图
Matplotlib 先写一个最简单的: import matplotlib.pyplot as plt plt.plot([1,4],[2,8]) #plot画折线图plt.show() 确定两个点画一条线 import matplotlib.pyplot as plt x[1,23,4,56,7,6] #x轴数据 y[22,44,56,67,43,2] #y轴数据 s[22,43,33,44,43,7] plt.p…...
Jetpack 各种框架简介
Jetpack是Google推出的一套为Android开发提供极大便利的组件、工具和指导集,旨在帮助开发者快速构建高质量的应用,并遵循最佳实践。 Jetpack不仅是一个提高开发效率的工具集,还是Android开发的未来方向。它通过整合各种组件和工具࿰…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
AD学习(3)
1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分: (1)PCB焊盘:表层的铜 ,top层的铜 (2)管脚序号:用来关联原理图中的管脚的序号,原理图的序号需要和PCB封装一一…...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
