题解 | #通讯网络#

一.题目描述
NC538通讯网络
n−1条道路连通的n座城市，城市两两之间有且只有一条路径，每条都道路都有一个权值w 。现在城市之间要建立通讯网络，两座城市之间通讯质量取决于链路所经路径的权值和，权值和越大则链路的通讯质量越高。一条路径被破坏后，经过这条路径的所有通讯线路均被破坏。牛牛想知道哪条道路一旦被破坏，对整个城市通讯网络的影响最大。输出为破坏一条道路后对城市通讯网络造成的最大影响。
图片说明
二.算法(搜索)

首先我们要理解题目，题目是一个n个点n-1条边的无向连通图，所以删去一条边那么整个连通图就会分成两部分，下面我们就来计算破坏一条边对城市网络造成的最大影响。对于两部分的图，我们假设其中有一个图中有a个点，则另一部分有n-a个点，那么造成的损失就是 $图片说明$ ,我们对所有边进行搜索，对最大值进行维护，返回最大值就可以了。对于左右两个部分的点的数量，我们可以用一个cnt数组去维护。下面是完整代码：

class Solution { 
    typedef long long int ll;
    typedef pair<int,int> PI;
private:
    int n;
    ll cnt[100005];
    vector<PI>mp[100005];
    ll mx=0;
public:
    void dfs(ll x,ll pre){
        cnt[x]=1;
        for(int i=0;i<mp[x].size();i++){
            ll nx=mp[x][i].first;
            ll w=mp[x][i].second;
            //nx是可达的下一个点 w表示边的权值
            if(nx==pre) continue;
            dfs(nx,x);
            cnt[x]+=cnt[nx];
            //删去该边对城市通讯网络造成的影响
            ll ans=cnt[nx]*(n-cnt[nx])*w;
            mx=max(mx,ans);
        }
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        this->n=n;//注意成员变量和函数变量相同所以要使用this指针
        for(int i=0;i<n-1;i++){
            int x=u[i];
            int y=v[i];
            int z=w[i];
            mp[x].push_back({y,z});
            mp[y].push_back({x,z});
        }
        dfs(1,0);
        return mx;
    }
};

时间复杂度： $O(n)$ 对每一个点都要访问一次
空间复杂度： $O(n)$ 需要额外空间对图进行存储
优缺点：空间赋值度高，但是思路简单
三.算法(链式前向星+java的实现)
看题解没有java的，所以就写了一下，在用Java的时候使用的是链式前向星存图，大家可以了解一下，下面是完整代码：

import java.util.*;
public class Solution {
    private static final int[] nx,h,e,wu,cn;
    private static long mx;
    private static int cnt;
    static{
        cnt=0;
        mx=0;
        nx=new int[100005];
        h=new int[100005];
        e=new int[100005];
        wu=new int[100005];
        cn=new int[100005];
        //这块一定要注意被数据卡坑了 h数组必须全部初始化为-1
        for(int i=0;i<100000;i++){
            h[i]=-1;
        }
    }
    //链式前向星
    void add(int a,int b,int c){
        e[cnt]=b;
        wu[cnt]=c;
        nx[cnt]=h[a];
        h[a]=cnt++;
    }
    void dfs(int x,int pre,int ed){
        cn[x]=1;
        for(int i=h[x];i!=-1;i=nx[i]){
            int v=e[i];
            int s=wu[i];
            //v表示可以到达的下一个结点
            if(v==pre) continue;//若是重复遍历之间跳过
            dfs(v,x,ed);
            cn[x]+=cn[v];
            //删除该边对整个通讯网络的影响
            long ans=cn[v]*(ed-cn[v])*s;
            //更新最大值
            mx=Math.max(mx,ans);
        }
    }
    public long solve (int n, int[] u, int[] v, int[] w) {
       for(int i=0;i<n-1;i++){
           //双向边存图
           add(u[i],v[i],w[i]);
           add(v[i],u[i],w[i]);
       }
        dfs(1,0,n);
        return mx;
    }
}

时间复杂度： $O(n)$ 对每一个点都要进行进行访问
空间复杂度： $O(n)$ 只需要一维数组进行存图
优缺点：代码思路简单但是实现起来复杂