通讯网络

[编程题]通讯网络

热度指数：737 时间限制：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$

算法知识视频讲解

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param n int整型 城市个数
   * @param u int整型vector 
   * @param v int整型vector 
   * @param w int整型vector 
   * @return long长整型
   */
  long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < u.size(); ++i) {
      g[u[i]].emplace_back(v[i], w[i]);
      g[v[i]].emplace_back(u[i], w[i]);
    }
    
    long long ans = 0;
    function<int(int, int)> depth_first_search_algorithm = 
            [&](int curr, int parent) -> int {
      
      int total = 1;
      for (const auto& [nxt, w] : g[curr]) {
        if (nxt == parent) continue;
        int cnt = depth_first_search_algorithm(nxt, curr);
        total += cnt;
        ans = max(ans, static_cast<long long>(w * cnt * (n - cnt)));
      }
      
      return total;
    };
    
    depth_first_search_algorithm(1, -1);
    return ans;
  }
};

发表于 2021-07-20 19:11:33 回复(0)

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param n int整型 城市个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @param w int整型vector 
     * @return long长整型
     */
    struct P{
        int v, w;
    };
    vector<P> Edge[100001];
    bool vis[100001];
    long long s = 0;
    long long DFS(int u, int n, bool *vis){
        if(vis[u])
            return 0;
        vis[u] = true;
        long long t = 0;
        for(auto &e: Edge[u]){
            long long m = DFS(e.v, n, vis);
            long long x = m * (n-m) * e.w;
            t += m;
            s = max(s, x);
        }
        return t+1;
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        for(int i=0;i<n-1;i++){
            Edge[u[i]].push_back({v[i], w[i]});
            Edge[v[i]].push_back({u[i], w[i]});
        }
        memset(vis, false, sizeof(vis));
        DFS(u[0], n, vis);
        return s;
    }
};

发表于 2020-08-26 01:42:37 回复(0)

C/C++

.晚安

class Solution {
public:
    /**
     * 
     * @param n int整型 城市个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @param w int整型vector 
     * @return long长整型
     */
    int dfs(int n, vector<vector<pair<int, int>>>& a, int pre, pair<int, int>& cur, long long& Max) {
        int N = 1;
        for (auto p: a[cur.first]) if (p.first != pre) N += dfs(n, a, cur.first, p, Max);
        long long b = (long long)N * (n - N) * cur.second;
        if (b > Max) Max = b;
        return N;
    }
    
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        vector<vector<pair<int, int>>> a(n, vector<pair<int, int>>());
        for (int i = 0; i < n - 1; i++) {
            a[--u[i]].push_back({--v[i], w[i]});
            a[v[i]].push_back({u[i], w[i]});
        }
        long long Max = 0;
        for (int i = 0; i < n; i++) {
            if (a[i].size() == 1) {
                dfs(n, a, i, a[i][0], Max);
                break;
            }
        }
        return Max;
    }
};

发表于 2020-07-28 23:16:06 回复(0)