題目描述

有一個(gè)無(wú)向無(wú)環(huán)連通圖成肘，每條邊通過(guò)兩個(gè)頂點(diǎn)x[i],y[i]來(lái)描述帘靡，每條邊的長(zhǎng)度通過(guò)d[i]來(lái)描述淆攻。求這樣的一個(gè)點(diǎn)p行嗤，使得其他點(diǎn)到p的距離和最小已日，如果有多個(gè)這樣的點(diǎn)p，返回編號(hào)最小的昂验。

思路點(diǎn)撥

dp[i] 代表以 i 為根的子樹中的結(jié)點(diǎn)到 i 結(jié)點(diǎn)的距離和捂敌，dp[i] = sum(dp[j] + np[j] * d(i, j))，np[i] 代表以 i 為根的子樹的所有結(jié)點(diǎn)的個(gè)數(shù)既琴，np[i] = sum(np[j]) + 1占婉。

考點(diǎn)分析

該題算是比較難的一道題了，無(wú)向無(wú)環(huán)的連通圖甫恩，我們可以理解為一棵多叉樹逆济，對(duì)于一棵多叉樹要求費(fèi)馬點(diǎn)，顯然需要樹形dp磺箕，不過(guò)這里我們需要dfs兩次奖慌，第一次先求出每個(gè)字?jǐn)?shù)的節(jié)點(diǎn)數(shù)np[i]和子樹中的結(jié)點(diǎn)到 i 結(jié)點(diǎn)的距離和dp[i],那么在第二個(gè)dfs中就能求出費(fèi)馬點(diǎn)的位置，具體的狀態(tài)轉(zhuǎn)移可以參考一下答案松靡。

參考程序

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

/**
* 本參考程序來(lái)自九章算法简僧，由 @華助教 提供。版權(quán)所有雕欺，轉(zhuǎn)發(fā)請(qǐng)注明出處岛马。
* - 九章算法致力于幫助更多中國(guó)人找到好的工作，教師團(tuán)隊(duì)均來(lái)自硅谷和國(guó)內(nèi)的一線大公司在職工程師屠列。
* - 現(xiàn)有的面試培訓(xùn)課程包括：九章算法班啦逆，系統(tǒng)設(shè)計(jì)班，算法強(qiáng)化班笛洛，Java入門與基礎(chǔ)算法班夏志，Android 項(xiàng)目實(shí)戰(zhàn)班，
* - Big Data 項(xiàng)目實(shí)戰(zhàn)班苛让，算法面試高頻題班, 動(dòng)態(tài)規(guī)劃專題班
* - 更多詳情請(qǐng)見官方網(wǎng)站：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;
    }
}