当前位置: 首页 > news >正文

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 1n100 1 ≤ m ≤ 1000 1 \le m \le 1000 1m1000,表示该无向图的节点数和边数。每个节点用 1 ∼ n 1 \sim n 1n 的整数编号。

接下来的 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 1c109

数据保证不会出现自回边和重边。注意:具有相同权值的边不会超过 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 1n100 1 ≤ m ≤ 1000 1 \le m \le 1000 1m1000 1 ≤ c i ≤ 1 0 9 1\leq c_i\leq 10^9 1ci109

先引入一个引理:

对于一个图的最小生成树,每个边权的边出现的次数是一样的

证明:模拟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 > < [空] > < [空] >取次花丛懒回顾&#xff0c;半缘修道…...

十分钟搭建一个RTMP服务器

使用SRS搭建RTMP服务器 如果您需要搭建一个RTMP服务器&#xff0c;您可以使用SRS&#xff08;Simple-RTMP-Server&#xff09;来完成此任务。SRS是一个开源的RTMP服务器下面是一个简单的步骤指南&#xff1a; 获取srs srs官⽹&#xff1a;https://github.com/ossrs/srs 码云…...

Spring Boot解决循环注入问题

Spring Boot解决循环依赖注入问题 代码问题回显启动错误日志解决方案&#xff1a;使用事件驱动或通过 ApplicationContext 手动获取 Bean1. 事件驱动设计2. 使用 ApplicationContext 手动获取 Bean3. 拆分逻辑 总结 代码问题回显 现有代码1 在InterestService中依赖MemberInte…...

《数据挖掘》期末考核重点

1.数据预处理的目的与形式 数据预处理的目的是提供干净&#xff0c;简洁&#xff0c;准确的数据&#xff0c;以达到简化模型和提高算法泛化能力的目的&#xff0c;使挖掘过程更有效&#xff0c;更容易&#xff0c;提高挖掘效率和准确性。 2.数据预处理的形式 数据清理&#…...

Golang | Leetcode Golang题解之第334题递增的三元子序列

题目&#xff1a; 题解&#xff1a; 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)…...

探索文件系统:高效、可靠的文件管理与访问机制

文件系统的功能规划 内存就像是一个书包&#xff0c;容量有限&#xff0c;只能带着一部分东西。而图书馆则是一个专门存储和管理文件的地方&#xff0c;拥有更大的容量&#xff0c;并且可以永久保存文件。为了能够快速找到需要的文件&#xff0c;我们需要有一个书单来记录每本…...

启程与远征Ⅸ--优化生成式人工智能以满足业务需求的框架

生成类似人类的文本和语音曾经只存在于科幻小说中。但 GPT-3 和 PaLM 等大型语言模型 (LLM) 的快速发展让这一愿景更接近现实&#xff0c;解锁了从聊天机器人到内容创作等一系列有前景的商业应用。 然而&#xff0c;通用基础模型往往无法满足行业用例的需求。企业对其生成式 A…...

canal数据同步工具介绍与应用

canal服务 canal介绍canal版本与环境canal 服务集canal应用场景&#xff1a; canal常见问题xml配置问题连接认证问题jar版本问题连接问题 canal介绍 ‌1、Canal是‌阿里巴巴开源的‌MySQL增量数据订阅和消费工具&#xff0c;通过模拟MySQL的‌slave与‌master交互&#xff0c;捕…...

ubuntu18.04 设置静态地址

修改配置文件 sudo vim /etc/netplan/01-network-manager-all.yaml 代码如下&#xff1a; network: version: 2 renderer: NetworkManager ethernets: ens33: # 配置的网卡名称&#xff0c;可以使用ifconfig -a查看本机的网卡 dhcp4: no # 关闭动态IP设置 …...

jira敏捷开发管理工具视频教程Confluence工作流协同开发(2024)

正文&#xff1a; 随着Jira敏捷开发方法论的普及&#xff0c;Jira已经成为全球软件开发团队管理项目、任务和问题的首选工具。为了帮助团队更好地掌握Jira的核心功能&#xff0c;精心准备了一套全面开发技术及案例视频教程——《Jira敏捷开发管理工具视频教程Confluenc…...

【网络】TCP回显服务器和客户端的构造,以及相关bug解决方法

文章目录 ServerSocket构造方法方法 Socket构造方法方法 回显服务器&#xff08;Echo Server&#xff09;1. 构造方法2. 建立连接processConnection 方法的创建1. 读取请求并解析2. 根据请求计算响应3. 把响应写回给客户端 3. 完整代码 客户端&#xff08;Echo Client&#xff…...

Python知识点:如何使用Boto3进行AWS服务管理

使用 boto3 来管理 AWS 服务是一个非常强大的方式&#xff0c;因为 boto3 是 AWS 提供的官方 Python SDK。下面是使用 boto3 管理 AWS 服务的基本步骤&#xff0c;包括设置、操作和常见的 AWS 服务示例。 1. 安装 boto3 首先&#xff0c;确保你已经安装了 boto3。可以使用 pi…...

Java - 正则表达式

Java 提供了 java.util.regex 包&#xff0c;它包含了 Pattern 和 Matcher 类&#xff0c;用于处理正则表达式的匹配操作。 正则表达式的模式 正则表达式的模式可以包括以下内容&#xff1a; 字面值字符&#xff1a;例如字母、数字、空格等&#xff0c;可以直接匹配它们自身。…...

Vue一款流行的JavaScript前端框架

1.Vue简介 Vue是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&#xff0c;并提供了一套声明式的、组件化的编程模型&#xff0c;帮助你高效地开发用户界面。无论是简单还是复杂的界面&#xff0c;Vue 都可以胜任。 Vue所关注的核心是MVC…...

GPT-SoVITS

文章目录 model archS1 ModelS2 model model arch S1 model: AR model–ssl tokensS2 model: VITS&#xff0c;ssl 已经是mel 长度线性相关&#xff0c;MRTE(ssl_codes_embs, text, global_mel_emb)模块&#xff0c;将文本加强相关&#xff0c;学到一个参考结果 S1 Model cla…...

linux高级编程——文件IO(常用函数大全)

1.相关介绍及常用函数 Linux高级编程中的目录IO操作是文件系统编程的一个重要组成部分&#xff0c;主要涉及到目录的打开、读取、遍历和关闭等操作。以下是一些基本的目录IO操作和相关的系统调用函数 1.1 opendir函数 打开目录&#xff1a;使用opendir函数打开一个目录&#…...

matplotlib画图

Matplotlib 先写一个最简单的&#xff1a; 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开发提供极大便利的组件、工具和指导集&#xff0c;旨在帮助开发者快速构建高质量的应用&#xff0c;并遵循最佳实践。 Jetpack不仅是一个提高开发效率的工具集&#xff0c;还是Android开发的未来方向。它通过整合各种组件和工具&#xff0…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...