首页 > 试题广场 >

通讯网络

[编程题]通讯网络

$n-1$ 条道路连通的 $n$ 座城市，城市两两之间有且只有一条路径，每条都道路都有一个权值 $w$ 。

现在城市之间要建立通讯网络，两座城市之间通讯质量取决于链路所经路径的权值和，权值和越大则链路的通讯质量越高。

一条路径被破坏后，经过这条路径的所有通讯线路均被破坏。

牛牛想知道哪条道路一旦被破坏，对整个城市通讯网络的影响最大。输出为破坏一条道路后对城市通讯网络造成的最大影响。

示例1

输入

5,[1,4,5,4],[5,1,2,3],[9,25,30,8]

经过第二条边的城市对有 （1,4), (1,3), (5, 4), (5, 3), (2, 4), (2, 3), 第二条边对通信网络的贡献为 25 * 6 = 150

城市 $u$ ，城市 $v$ ，权值 $w$ 。

对于这三行中的第 i 个数，分别表示城市 $u_i$ 与城市 $v_i$ 之间有一条权值为 $w_i$ 的道路。

$1 \leq n \leq 100,000,\quad 1 \leq w \leq 1,000,000$

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

dfs

难度：

0条回答 8收藏 4184浏览

查看代码

通讯网络

扫一扫，把题目装进口袋