3067. 在带权树网络中统计可连接服务器对数目 Medium

2024-06-04 17:52

本文主要是介绍3067. 在带权树网络中统计可连接服务器对数目 Medium,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给你一棵无根带权树,树中总共有 n 个节点,分别表示 n 个服务器,服务器从 0 到 n - 1 编号。同时给你一个数组 edges ,其中 edges[i] = [ai, bi, weighti] 表示节点 ai 和 bi 之间有一条双向边,边的权值为 weighti 。再给你一个整数 signalSpeed 。

如果两个服务器 a ,b 和 c 满足以下条件,那么我们称服务器 a 和 b 是通过服务器 c 可连接的 :

 ·a < b ,a != c 且 b != c 。

 ·从 c 到 a 的距离是可以被 signalSpeed 整除的。

 ·从 c 到 b 的距离是可以被 signalSpeed 整除的。

 ·从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边。

请你返回一个长度为 n 的整数数组 count ,其中 count[i] 表示通过服务器 i 可连接 的服务器对的 数目 。

示例 1:

输入:edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1
输出:[0,4,6,6,4,0]
解释:由于 signalSpeed 等于 1 ,count[c] 等于所有从 c 开始且没有公共边的路径对数目。
在输入图中,count[c] 等于服务器 c 左边服务器数目乘以右边服务器数目。

示例 2:

输入:edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3
输出:[2,0,0,0,0,0,2]
解释:通过服务器 0 ,有 2 个可连接服务器对(4, 5) 和 (4, 6) 。
通过服务器 6 ,有 2 个可连接服务器对 (4, 5) 和 (0, 5) 。
所有服务器对都必须通过服务器 0 或 6 才可连接,所以其他服务器对应的可连接服务器对数目都为 0 。

提示:

 ·2 <= n <= 1000

 ·edges.length == n - 1

 ·edges[i].length == 3

 ·0 <= ai, bi < n

 ·edges[i] = [ai, bi, weighti]

 ·1 <= weighti <= 106

 ·1 <= signalSpeed <= 106

 ·输入保证 edges 构成一棵合法的树。

题目大意:计算每个结点可连接的服务器对数。

分析:

(1)将某个结点看作根,只有该结点有多个子树时,该结点才有可连接的服务器对,否则由于其余服务器到该结点有公共边,该结点可连接的服务器对数为0;

(2)基于(1)中结论,某个结点可连接的服务器对数ans[i]计算方式如下(将与该结点的距离是signalSpeeed倍数的结点称之为符合要求的结点):用深度优先遍历算法计算每个子树符合要求的结点个数,ans[i]即为这些子树中符合要求的结点进行交叉配对最多可以配对的服务器对数;

(3)根据(2)中算法可以得到1个结点可连接的对数,采取相同做法对每个结点进行深度优先遍历就能计算得到每个结点可连接的服务器对数;

(4)本题结点较多,采用邻接矩阵存储时间复杂度较高,为O(N3),会超时,但所给数据结构是树,只有n-1条边,考虑到边较少,因此采用邻接表存储,将时间复杂度降为O(N2)。

class Solution {
public:vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {int N=edges.size()+1,sumNode,sum;vector<vector<pair<int,int>>> dis(N);vector<int> ans(N,0);function<int(int,int,int)> dfs=[&](int root,int parent,int length){int num=0;if(!length) ++num;for(auto& [node,len]:dis[root]){if(node!=parent) num+=dfs(node,root,(length+len)%signalSpeed);}return num;};for(auto& ele:edges){dis[ele[0]].emplace_back(ele[1],ele[2]);dis[ele[1]].emplace_back(ele[0],ele[2]);}for(int i=0;i<N;++i){sum=0;for(auto& [root,len]:dis[i]){sumNode=dfs(root,i,len%signalSpeed);ans[i]+=sumNode*sum;sum+=sumNode;}}return ans;}
};
//邻接矩阵存储,超时的算法
// class Solution {
// public:
//     vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
//         int N=edges.size()+1,sumNode,sum;
//         vector<vector<int>> dis(N,vector<int>(N,0));
//         vector<int> ans(N,0);
//         function<int(int,int,int)> dfs=[&](int node,int parent,int length){
//             int num=0;
//             length+=dis[parent][node];
//             if(!(length%signalSpeed)) ++num;
//             for(int i=0;i<dis.size();++i){
//                 if(dis[node][i]>0&&i!=parent) num+=dfs(i,node,length);
//             }
//             return num;
//         };
//         for(int i=0;i<N-1;++i) dis[edges[i][0]][edges[i][1]]=dis[edges[i][1]][edges[i][0]]=edges[i][2];
//         for(int i=0;i<N;++i){
//             sum=0;
//             for(int j=0;j<N;++j){
//                 if(dis[i][j]>0){
//                     sumNode=dfs(j,i,0);
//                     ans[i]+=sumNode*sum;
//                     sum+=sumNode;
//                 }
//             }
//         }
//         return ans;
//     }
// };

这篇关于3067. 在带权树网络中统计可连接服务器对数目 Medium的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

python连接本地SQL server详细图文教程

《python连接本地SQLserver详细图文教程》在数据分析领域,经常需要从数据库中获取数据进行分析和处理,下面:本文主要介绍python连接本地SQLserver的相关资料,文中通过代码... 目录一.设置本地账号1.新建用户2.开启双重验证3,开启TCP/IP本地服务二js.python连接实例1.

基于Python打造一个可视化FTP服务器

《基于Python打造一个可视化FTP服务器》在日常办公和团队协作中,文件共享是一个不可或缺的需求,所以本文将使用Python+Tkinter+pyftpdlib开发一款可视化FTP服务器,有需要的小... 目录1. 概述2. 功能介绍3. 如何使用4. 代码解析5. 运行效果6.相关源码7. 总结与展望1

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经

Ubuntu中远程连接Mysql数据库的详细图文教程

《Ubuntu中远程连接Mysql数据库的详细图文教程》Ubuntu是一个以桌面应用为主的Linux发行版操作系统,这篇文章主要为大家详细介绍了Ubuntu中远程连接Mysql数据库的详细图文教程,有... 目录1、版本2、检查有没有mysql2.1 查询是否安装了Mysql包2.2 查看Mysql版本2.

Python3.6连接MySQL的详细步骤

《Python3.6连接MySQL的详细步骤》在现代Web开发和数据处理中,Python与数据库的交互是必不可少的一部分,MySQL作为最流行的开源关系型数据库管理系统之一,与Python的结合可以实... 目录环境准备安装python 3.6安装mysql安装pymysql库连接到MySQL建立连接执行S

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Spring Boot 整合 MyBatis 连接数据库及常见问题

《SpringBoot整合MyBatis连接数据库及常见问题》MyBatis是一个优秀的持久层框架,支持定制化SQL、存储过程以及高级映射,下面详细介绍如何在SpringBoot项目中整合My... 目录一、基本配置1. 添加依赖2. 配置数据库连接二、项目结构三、核心组件实现(示例)1. 实体类2. Ma