通讯网络

通讯网络

https://www.nowcoder.com/questionTerminal/313783d094ec41d49215ffa2097d9b54

思路

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

如下图所示:
图片说明

Code

class Solution {
#define ll long long
#define maxn 100010
#define pii pair<int, int>
private:
    int n;
    int sz[maxn];  // sz[x] 表示结点 x 的子树结点数量
    ll ans;
    vector<pii> g[maxn];  // 保存边。

public:
    void dfs(int x, int fa = 0) {
        sz[x] = 1;
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            dfs(v, x);
            sz[x] += sz[v];
            ll tmp = 1ll * sz[v] * (n - sz[v]) * w;  // 计算该边对链路的影响
            ans = max(ans, tmp);
        }
    }

    ll solve(int n, vector<int> u, vector<int> v, vector<int> w) {
        this->n = n;
        for (int i = 1; i < n; ++i) {
            int a = u[i - 1], b = v[i - 1], c = w[i - 1];
            g[a].push_back({b, c});
            g[b].push_back({a, c});
        }
        dfs(1);
        return ans;
    }

};
全部评论

相关推荐

专心打鱼:互联网搬运工,贴子都要偷
点赞 评论 收藏
分享
评论
1
1
分享
牛客网
牛客企业服务