算法 DFS

题目描述

题面

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

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

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

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

输入

第一行一个正整数 nn。

接下来 3 行，每行n−1 个正整数。

依次是城市 u，城市 v， 权值 w 。

对于这三行中的第 i 个数，分别表示城市u[i]与城市 v[i]之间有一条权值为 w[i] 的道路。

 

输出

破坏一条道路后对城市通讯网络造成的最大影响。

示例1

输入

复制

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

输出

复制

150

说明

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

 

 

常规做法，对于每条边，其左右城市的数目之积*权重    采用备忘录方式记录下  p->q方向所有能经过的城市数目

 

class Solution {
public:
    /**
     * 
     * @param n int整型 城市个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @param w int整型vector 
     * @return long长整型
     */

    
    vector<int> a[100000];//a[i]存放第i个城市所有直接相连的城市数组
    //备忘录方法
    int dfs_res[10000][10000];
    bool visit[100000];//访问数组
    
    int DFS(int p,int q)//返回从p点开始沿着q城市方向所能访问到所有城市个数(不包括p城市)
    {
        if(dfs_res[p][q])
            return dfs_res[p][q];
        int res=1;
        visit[p]=true;
        visit[q]=true;
        for(int i=0;i<a[q].size();i++) //遍历所有p的连线
        {
            if(visit[a[q][i]]==false) //没有访问过
            {
                res+=DFS(q,a[q][i]);
            }
        }
        dfs_res[p][q]=res;
        return res;
           
    }
  
    

    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        // write code here
        for(int i=0;i<n-1;i++)
        {
            a[u[i]].push_back(v[i]);//构建联通量
            a[v[i]].push_back(u[i]);
        }
        long long res=0;
        for(int i=0;i<n-1;i++) //遍历每一条边
        {
            memset(visit,0,sizeof(visit));
            int left_num=DFS(u[i],v[i]);//左边点的数目
            memset(visit,0,sizeof(visit));
            int right_num=DFS(v[i],u[i]);//右边点的数目
            long long temp=left_num*right_num*w[i];
            res=max(res,temp);
            
            
        }
        
        return res;
     
    }
};

进一步发现，对于每一条边，其左右两侧一定是两颗树

 

采用DFS方式进行遍历即可，记录下中间的子节点数目

关键函数   dfs(int x,int father=0) 表示 x所有子节点数目（包含x ） 其依赖于来自的方向，由其父亲节点决定 

class Solution {
public:
    /**
     * 
     * @param n int整型 城市个数
     * @param u int整型vector 
     * @param v int整型vector 
     * @param w int整型vector 
     * @return long长整型
     */

    long long res[100000];//res[i]存放城市i的子节点数目
    vector<pair<int,int>> a[100000];//a[i]存放所有i城市的直接到达城市及其权重
    long long my_max=0;
    int city_num=0;
    void dfs(int x,int father=0)  //从x节点开始遍历其子节点，其依赖父亲是father
    {
        res[x]=1;
        for(int i=0;i<a[x].size();i++) //访问其所有子树
        {
            int son=a[x][i].first;
            int weight=a[x][i].second;
            if(son==father)
                continue;
            dfs(son,x);
            res[x]+=res[son];
            my_max=max(my_max,res[son]*(city_num-res[son])*weight);//记录该条边的权重影响
        }
      
    
    }
   
    

    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        // write code here
        
        city_num=n;
        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]});
            
        }
        dfs(1);
        return my_max;
     
    }
};