通讯网络

[编程题]通讯网络

热度指数：738 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$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$

算法知识视频讲解

未来0116

发表于 2021-08-12 11:29:51

一.题目描述NC538通讯网络n−1条道路连通的n座城市，城市两两之间有且只有一条路径，每条都道路都有一个权值w 。现在城市之间要建立通讯网络，两座城市之间通讯质量取决于链路所经路径的权值和，权值和越大则链路的通讯质量越高。一条路径被破坏后，经过这条路径的所有通讯线路均被破坏。牛牛想知道哪条道路一旦展开全文

szki

发表于 2020-02-15 13:06:16

思路假设总共个城市构成了一棵树，任意一条边，都会将城市分成两部分，假设左边有个，则右边有个，那么左侧的每个城市和右侧的每个城市都会相连，即经过该边次，一旦被破坏，造成的损失是，只需在dfs过程中取一下每条边贡献的最大值即可，时间复杂度。如下图所示： Code class 展开全文

摸鱼学大师

发表于 2021-08-06 17:49:14

思路：题目的主要信息： n个节点，n-1条边，使之全部连通，这就是一棵树权值就是通话质量，任意去掉一条边，求影响的最大的通话质量（有n个城市受影响，就要用n乘上去掉边的权值）即影响的城市数为去掉边后两个子树节点数相乘，因此我们找到，其中是去掉权值为的边后子树的节点数。这道题需要求子树的展开全文

AimerAimer

发表于 2021-10-12 20:55:37

题意：有一棵节点为 n 的树，树的每条边都有一个权值 w 。每条边都有一个重要程度：展开全文

牛客313925129号

发表于 2021-08-11 17:11:08

题目理解 n个城市对应n个结点，城市之间的路径对应结点之间的边。我们删除某一条边。假设有m条两点之间的路径经过该边，该边的权值为w[i]，输出为m*w[i]的最大值。方法一对于题意的理解，我们删除一条边，其权重为w[i]；如果在原来的图中，有m条路径包含了该边，则最后输出代价为w[i]*m。那m 展开全文