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

相关文章

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

W外链微信推广短连接怎么做?

制作微信推广链接的难点分析 一、内容创作难度 制作微信推广链接时,首先需要创作有吸引力的内容。这不仅要求内容本身有趣、有价值,还要能够激起人们的分享欲望。对于许多企业和个人来说,尤其是那些缺乏创意和写作能力的人来说,这是制作微信推广链接的一大难点。 二、精准定位难度 微信用户群体庞大,不同用户的需求和兴趣各异。因此,制作推广链接时需要精准定位目标受众,以便更有效地吸引他们点击并分享链接

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

ASIO网络调试助手之一:简介

多年前,写过几篇《Boost.Asio C++网络编程》的学习文章,一直没机会实践。最近项目中用到了Asio,于是抽空写了个网络调试助手。 开发环境: Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议: UDP + TCP Client + TCP Server 独立的Asio(http://www.think-async.com)只包含了头文件,不依

poj 3181 网络流,建图。

题意: 农夫约翰为他的牛准备了F种食物和D种饮料。 每头牛都有各自喜欢的食物和饮料,而每种食物和饮料都只能分配给一头牛。 问最多能有多少头牛可以同时得到喜欢的食物和饮料。 解析: 由于要同时得到喜欢的食物和饮料,所以网络流建图的时候要把牛拆点了。 如下建图: s -> 食物 -> 牛1 -> 牛2 -> 饮料 -> t 所以分配一下点: s  =  0, 牛1= 1~

poj 3068 有流量限制的最小费用网络流

题意: m条有向边连接了n个仓库,每条边都有一定费用。 将两种危险品从0运到n-1,除了起点和终点外,危险品不能放在一起,也不能走相同的路径。 求最小的费用是多少。 解析: 抽象出一个源点s一个汇点t,源点与0相连,费用为0,容量为2。 汇点与n - 1相连,费用为0,容量为2。 每条边之间也相连,费用为每条边的费用,容量为1。 建图完毕之后,求一条流量为2的最小费用流就行了

poj 2112 网络流+二分

题意: k台挤奶机,c头牛,每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵,求最小化牛的最大路程。 解析: 最大值最小化,最小值最大化,用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程,匹配中的判断是在这个最大路程下,是否牛的数量达到c只。 如何求牛的数量呢,用网络流来做。 从源点到牛引一条容量为1的边,然后挤奶机到汇点引一条容量为m的边

Linux服务器Java启动脚本

Linux服务器Java启动脚本 1、初版2、优化版本3、常用脚本仓库 本文章介绍了如何在Linux服务器上执行Java并启动jar包, 通常我们会使用nohup直接启动,但是还是需要手动停止然后再次启动, 那如何更优雅的在服务器上启动jar包呢,让我们一起探讨一下吧。 1、初版 第一个版本是常用的做法,直接使用nohup后台启动jar包, 并将日志输出到当前文件夹n

Java 连接Sql sever 2008

Java 连接Sql sever 2008 /Sql sever 2008 R2 import java.sql.Connection; import java.sql.DriverManager; import java.sql.ResultSet; import java.sql.Statement; public class TestJDBC