首页 > 试题广场 >

最长路径

[编程题]最长路径

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

城市 $A$ 新建了 $n$ 个座房子，城市规划处用 $n-1$ 条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。

示例1

输入

7,[2,3,5,4,5,5],[5,2,1,6,7,4],[15,6,14,4,1,6]

输出

说明

当牛牛和牛妹分别被分到  ,  两个房子时，路径最长。

备注:

房子  , 房子  , 街道长度 。
表示房子  与房子  之间有一条长度为 的道路相连。
 。

算法知识视频讲解

C++

勇敢牛牛，不怕困难！

using PII = pair<int, int>;

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) {
    // build the undirected graph
    vector<vector<PII>> g(n + 1); 
    for (int i = 0; i < n - 1; ++i) {
      g[u[i]].emplace_back(v[i], w[i]);
      g[v[i]].emplace_back(u[i], w[i]);
    }
    // 两次bfs算法
    return breadth_first_search_algorithm(g, n, 
                                          breadth_first_search_algorithm(g, n, 1).first).second;
  }
  
private:
  
  pair<int, long long> breadth_first_search_algorithm(vector<vector<PII>>& g,
                                     const int n,
                                     int start) {
    deque<PII> q;
    vector<int> seen(n + 1);
    q.emplace_back(start, 0);
    seen[start] = 1;
    
    int max_dist_node, max_dist = 0;
    while (not q.empty()) {
      const auto [cur, dist] = q.front(); q.pop_front();
      if (dist > max_dist) {
        max_dist_node = cur;
        max_dist = dist;
      }
      for (const auto [nei, d] : g[cur]) {
        if (seen[nei]++) continue;
        q.emplace_back(nei, dist + d);
      }
    }
    
    return { max_dist_node, max_dist };
  }
};

发表于 2021-07-19 19:13:17 回复(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 Edge{
        int v, w;
    };
    vector<Edge> G[200003];
    long long Max = 0;
    long long DFS(int u, int pre){
        long long s = 0;
        for(auto &e: G[u]){
            if(e.v != pre){
                long long t = DFS(e.v, u) + e.w;
                Max = max(Max, s+t);
                s = max(s, t);
            }
        }
        return s;
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        for(int i=0;i<u.size();i++){
            G[u[i]].push_back({v[i], w[i]});
            G[v[i]].push_back({u[i], w[i]});
        }
        DFS(1, -1);
        return Max;
    }
};

发表于 2020-08-29 16:50:58 回复(0)

C++

云海翻腾

//n个节点n-1个连接，实际为树
//求任意两个节点的最大路径方式：
//从任一节点（当作根）出发对树进行深度优先遍历求出最大路径对应的叶子节点
//从该叶子节点（当作根）出发再次对树进行深度优先遍历求出最大路径即可

class Solution {
public:
long long dfsSearch(int n, const vector<vector<int> > &arr, int node, int parent, int &maxLenLeaf, int len)
{
bool bHasChild = false;
for (int i = 1; i <= n; i++)
{
if (i == node || i == parent || arr[node][i] == 0)
continue;

bHasChild = true;
dfsSearch(n, arr, i, node, maxLenLeaf, len + arr[node][i]);
}

if (!bHasChild)
{
if (len > m_maxLen)
{
m_maxLen = len;
maxLenLeaf = node;
}
}

return m_maxLen;
}

long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
if (n <= 1 || (int)u.size() != n - 1 || (int)v.size() != n - 1 || (int)w.size() != n - 1)
{
return 0;
}
vector<int> tmp(n + 1);
vector<vector<int> > arr(n + 1);
for (int i = 0; i < n + 1; i++)
{
arr[i] = tmp;
}

for (int i = 0; i < n - 1; i++)
{
arr[u[i]][v[i]] = w[i];
arr[v[i]][u[i]] = w[i];
}

m_maxLen = 0;
int node;
dfsSearch(n, arr, 1, -1, node, 0);
return dfsSearch(n, arr, node, -1, node, 0);
}
private:
long long m_maxLen;
};

发表于 2021-09-30 15:55:42 回复(0)

Python 3

ZhongHaoWang

等价于找树的直径

import collections
class Solution:
    def solve(self, n, u, v, w):
        # write code here
        edges = collections.defaultdict(list)
        dis = {}
        k = len(u)
        for i in range(k):
            edges[u[i] - 1].append(v[i] - 1)
            edges[v[i] - 1].append(u[i] - 1)
            dis[(v[i] - 1, u[i] - 1)] = w[i]
            dis[(u[i] - 1, v[i] - 1)] = w[i]

        node, d = -1, 0

        def dfs(cur_node, cur_dis, visited):
            nonlocal node, d, edges
            if cur_dis > d:
                node = cur_node
                d = cur_dis
            for next_ in edges[cur_node]:
                if next_ not in visited:
                    visited.append(next_)
                    dfs(next_, cur_dis + dis[(cur_node, next_)], visited)
            return

        dfs(0,0,[0])
        dfs(node,0,[node])
        return d

发表于 2021-08-29 18:42:00 回复(0)

Java

百步飞剑️

Java dfs通过率70%，会堆栈溢出

public class Solution {

    private long maxRes = 0;
    private ArrayList<ArrayList<Node>> nodes;

    /**
     * 返回最终结果
     *
     * @param n int整型 城市数量
     * @param u int整型一维数组
     * @param v int整型一维数组
     * @param w int整型一维数组
     * @return long长整型
     */
    public long solve(int n, int[] u, int[] v, int[] w) {
        // write code here
        nodes = new ArrayList<>(n + 1);
        for(int i = 0; i <= n; i++) {
            nodes.add(new ArrayList<>());
        }
        for(int i = 0; i < u.length; i++) {
            nodes.get(u[i]).add(new Node(v[i], w[i]));
            nodes.get(v[i]).add(new Node(u[i], w[i]));
        }
        dfs(1, -1);
        return maxRes;
    }

    long dfs(int toIndex, int fromIndex) {
        long subMax = 0;
        for(Node node : nodes.get(toIndex)) {
            if (node.index != fromIndex) {
                long curSubNum = dfs(node.index, toIndex) + node.weight;
                maxRes = Math.max(maxRes, subMax + curSubNum);
                subMax = Math.max(subMax, curSubNum);
            }
        }
        return subMax;
    }

    static class Node {
        int index;
        int weight;

        public Node(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }
｝

发表于 2020-09-13 21:38:25 回复(0)

Java

烟酒僧不烟酒

Java暴力dfs只能通过40%多，想不出来怎么优化了。。。

import java.util.*;


public class Solution {
    long  maxLength = 0;
    /**
     * 返回最终结果
     * @param n int整型 城市数量
     * @param u int整型一维数组 
     * @param v int整型一维数组 
     * @param w int整型一维数组 
     * @return long长整型
     */
    public long solve (int n, int[] u, int[] v, int[] w) {
        // write code here
        //可以使用dfs
        //首先存储每个房子能够连接哪些房子，并且长度是多少
        Map<Integer,Map<Integer,Integer>> map = new HashMap<>();
        for(int i = 0;i<n-1;i++){
            if(!map.containsKey(u[i])){
                map.put(u[i],new HashMap<>());
            }
            map.get(u[i]).put(v[i],w[i]);
            if(!map.containsKey(v[i])){
                map.put(v[i],new HashMap<>());
            }
            map.get(v[i]).put(u[i],w[i]);
        }
        //此时可以遍历进行dfs
        for(int i = 1;i<=n;i++){
            //这里可以优化，最长路径肯定是从叶子节点开始的
            if(map.get(i).size()==1){
                getLong(map,new HashSet<Integer>(),i,0);
            }
        }
        return maxLength;
    }
    public void getLong(Map<Integer,Map<Integer,Integer>> map,Set<Integer> usedSet,int start,int maxLen){
        maxLength = Math.max(maxLength,maxLen);
        for(int i : map.get(start).keySet()){
            if(!usedSet.contains(i)){
                maxLen += map.get(start).get(i);
                usedSet.add(start);
                getLong(map,usedSet,i,maxLen);
                usedSet.remove(start);
                maxLen -= map.get(start).get(i);
            }
        }
    }
}

发表于 2020-07-07 12:19:46 回复(0)