九章算法 | Google 面试题：Fermat Point of Graphs

撰文 | JZ
专栏 | 九章算法

题目描述

有一个无向无环连通图，每条边通过两个顶点x[i],y[i]来描述，每条边的长度通过d[i]来描述。求这样的一个点p，使得其他点到p的距离和最小，如果有多个这样的点p，返回编号最小的。

思路点拨

dp[i] 代表以 i 为根的子树中的结点到 i 结点的距离和，dp[i] = sum(dp[j] + np[j] * d(i, j))，np[i] 代表以 i 为根的子树的所有结点的个数，np[i] = sum(np[j]) + 1。

考点分析

该题算是比较难的一道题了，无向无环的连通图，我们可以理解为一棵多叉树，对于一棵多叉树要求费马点，显然需要树形dp，不过这里我们需要dfs两次，第一次先求出每个字数的节点数np[i]和子树中的结点到 i 结点的距离和dp[i],那么在第二个dfs中就能求出费马点的位置，具体的状态转移可以参考一下答案。

九章参考程序

https://www. jiuzhang.com/solution/f ermat-point-of-graphs/

/**
* 本参考程序来自九章算法，由 @华助教 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    /**
     * @param x: The end points set of edges
     * @param y: The end points set of edges
     * @param d: The length of edges
     * @return: Return the index of the fermat point
     */
    class Pair {
        public int first;
        public int second;
        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    } 
    long ans;
    int idx;
     
    void dfs1(int x, int f, List<List<Pair>> g, int[] np, long[] dp) {
        np[x] = 1;
        dp[x] = 0;
        for (int i = 0; i < g.get(x).size(); i++) {
            int y = g.get(x).get(i).first;
            if (y == f) {
                continue;
            }
            dfs1(y, x, g, np, dp);
            np[x] += np[y];
            dp[x] += dp[y] + (long)g.get(x).get(i).second * np[y];
        }
    }
    void dfs2(int x, int f, long sum, List<List<Pair>> g, int[] np, long[] dp, int n) {
        for (int i = 0; i < g.get(x).size(); i++) {
            int y = g.get(x).get(i).first;
            if (y == f) {
                continue;
            }
            long nextSum = dp[y] + (sum - dp[y] - (long)np[y] * g.get(x).get(i).second) + (long)(n - np[y]) * g.get(x).get(i).second;
            if (nextSum < ans || (nextSum == ans && x < idx)) {
                ans = nextSum;
                idx = y;
            }
            dfs2(y, x, nextSum, g, np, dp, n);
        }
    }
     
    public int getFermatPoint(int[] x, int[] y, int[] d) {
        // Write your code here
        int n = x.length + 1;
        List<List<Pair>> g = new ArrayList<List<Pair>>();
        for(int i = 0; i <= n; i++) {
            g.add(new ArrayList<Pair>());
        }
        for (int i = 0; i < x.length; i++) {
            g.get(x[i]).add(new Pair(y[i], d[i]));
            g.get(y[i]).add(new Pair(x[i], d[i]));
        }
        int [] np = new int[n + 1];
        long [] dp = new long[n + 1];
        dfs1(1, 0, g, np, dp);
        ans = dp[1];
        idx = 1;
        dfs2(1, 0, dp[1], g, np, dp, n);
        return idx;
    }
}